二分查找两个模板，leetcode35.搜索插入位置-Toy模板网

这篇具有很好参考价值的文章主要介绍了二分查找两个模板，leetcode35.搜索插入位置。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

二分法思想

在有序数列中，查找某个元素是否存在
扩展一下： 在有序数列中(通常是非递减，可以有重复元素)，查找第一个满足xx条件的元素
每次搜索区间减半，时间复杂度 $O (l o g n)$

模板1：有序数组中，查找是否存在某个元素，找到返回位置，找不到返回-1

public int binarySearch(int[] nums, int target) {
    //初始左、右边界，覆盖完整位置
    int left = 0;
    int right = nums.length - 1;
    int mid;
    while (left <= right) {
        mid = left + (right - left) / 2; // 避免int溢出
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return -1;
}

1.初始边界为0和n-1，如果你的下标从1开始，那就是1和n，效果一样，只需要确保初始闭区间一定能覆盖可能的位置
2.更新机制，匹配就返回mid，否则mid+1或mid-1。区间更新时不用带上mid，因为当前mid位置不匹配，所以mid不在下一轮查询的考虑范围之内。
3.深究一下： 条件为什么是left<=right？
如果条件改成left<right，考虑一种情况：target=4，数组为1,2,3,4,5，left=2指向3，right=3指向4，进入循环：
mid=2，nums[mid]<target
left=3
此时left==right，退出循环，返回-1。没找到，错误！！
而如果条件是left<=right：
mid=3
nums[mid]==target，成功找到！

所以单纯找元素是否存在，条件是<=

模板2：有序数组中(非递减，可以有重复元素)，查找第一个满足xx条件(以>=5为例)的元素的位置。如果不存在，给出假设该元素存在的正确位置。

public int binarySearch(int[] nums) {
	int target = 5;//例子，找第一个>=5
    int left = 0;
    int right = nums.length;//注意没有-1
    int mid;
    while (left < right) {
        mid = left + (right - left) / 2;
        if (nums[mid] >= target) {//这里就是条件
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

与模板1相比，有4个区别：
1.初始right，多一个
2.循环条件，是<不是<=
3.边界更新机制
4.返回值

1.初始right为什么不-1？因为要考虑所有可能得位置，如果target不存在，且比数组中所有元素都要大，那应该插入到最后一个位置，是n，不是n-1。
2、3、4举一个例子说明：1,2,3,5,6找4
初始left=0指向1，right=5指向6后面
mid=2, 3<4，left=3
mid=4, 6>4, right=4
mid=3, 5>4, right=3
left==right，退出循环
返回left=3
以上过程是正确的

如果循环条件是<=呢？
left=3, right=3
mid=3, 5>4, right=3
…
死循环了

再解释一下更新机制：
当nums[mid]>=target，因为我们要找第一个满足条件的，有可能在mid之前吧，所以要在left~mid搜索。但mid之前也有可能没啦，所以搜索区间不能把mid丢了。 因此更新方法为right=mid
当nums[mid]<target，显然mid不满足，答案一定是>=mid+1，区间更新时不需要再保留mid了。
一句话概括：更新下一轮循环的左、右时，一定要保证[左, 右]这个闭区间能覆盖所有的答案可能位置。

咱们这个模板是闭区间实现的，也有开区间的版本，自行研究。

最后说明一下返回值，
返回left，其实并不保证nums[left]==target。若target不存在，left是假设存在，该插在的位置。
因此，如果需要确定有没有搜索到，还得判断一下返回值nums[left]==target