乐趣区

关于leetcode算法:leetcode35

jiezi

这道题目能够使用暴力的解法，不过暴力的效率不够高，因而能够采纳二分查找，题目连贯间接给出：https://leetcode.cn/problems/search-insert-position/description/

通常的整数二分模板是如下这样的：

bool check(int x) {/*...*/} // 查看 x 是否满足某种性质

// 区间 [l, r] 被划分成 [l, mid] 和[mid+1, r]时应用：int bsearch_1(int l, int r) {while(l < r) {int mid = l+r>>1; // 若产生整数溢出 改为 l+(r-l>>1)
        if(check(mid)) r = mid; //check 判断 mid 是否满足性质
        else l = mid+1;
    }
}

// 区间 [l, r] 被划分成 [l, mid-1] 和[mid, r]时应用：int bsearch_2(int l, int r) {while(l < r) {int mid = l+r+1>>1; // 若产生整数溢出 改为 l+(r+1-l>>1)
        if(check(mid)) l = mid;
        else r = mid-1;
    }
}

能够发现区间边界的划分，不是 mid+1 就是mid-1，因而这个模板对这道题不太可行，所以独自记录下本题目标二分思路。

二分查找波及的很多的边界条件，逻辑比较简单，就是写不好。置信很多同学对二分查找法中边界条件解决不好。例如到底是 while(left < right) 还是 while(left <= right)，到底是right = middle 呢，还是要 right = middle - 1 呢？这里弄不分明次要是因为对区间的定义没有想分明，这就是不变量。要在二分查找的过程中，放弃不变量，这也就是循环不变量（感兴趣的同学能够查一查）。

以这道题目来举例，以下的代码中定义 target 是在一个在左闭右闭的区间里，也就是[left, right]（这个很重要）。这就决定了这个二分法的代码如何去写，大家看如下代码。要认真看正文，思考为什么要写while(l <= r)，为什么要写r = m - 1。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        // 1. 暴力版本
        // int n = nums.size();
        // for(int i = 0; i < n; ++i) {//     if(nums[i] >= target) return i;
        // }
        // return n;

        // 2. 二分版本
        int n = nums.size();
        int l = 0, r = n-1; // 定义 target 在左闭右闭的区间里，[l, r]
        while(l <= r) {// 当 l == r，区间 [l, r] 仍然无效
            int m = (l+r) >> 1;
            if(nums[m] < target) l = m+1; // target 在左区间，所以[l, m-1]
            if(nums[m] > target) r = m-1; // target 在右区间，所以[m+1, r]
            if(nums[m] == target) return m;
        }

        // 分为以下三种状况思考：// 目标值在数组所有元素之前，即最左侧，取 l
        // 目标值等于数组中元素的值 间接 return m
        // 目标值在数组某个元素的右侧以及在所有元素之后，即最右侧 取 l
        return l;
    }
};

当然下面的写法是以 l 为例，且区间为左右均闭，更多写法可参考：https://programmercarl.com/0035.%E6%90%9C%E7%B4%A2%E6%8F%92%E…

退出移动版