写一个二分查找会有多少bug？

哈哈服了写个二分查找写出了一堆问题，来看你写的破代码！🥰🥰

原代码

public int searchInsert(int[] nums, int target) {
    int len = nums.length;
    int left = 0, right = len - 1;
    int mid = (left + right) / 2 + 1;
    while (left < right) {
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid;
        if (nums[mid] > target) right = mid;
    }
    return mid;
}

问题分析！

重要的确定你的区间是 [ , ] 还是 [ , )，这会影响 mid、left、right 的更改

1. 初始 mid 计算错误： mid 不正确，应在每次循环内计算 mid。

int mid = left + (right - left) / 2;

1. 循环条件错误：在进行二分查找时，应该使用 <=

这里是因为你设置的区间是 [left,right]，=的时候有意义，所以是<=

while (left <= right) {

1. mid 更新逻辑错误： 更新 left 和 right 时，不应将 mid 直接赋值给 left 或 right，应调整为 mid + 1 或 mid - 1，否则可能会导致死循环

if (nums[mid] < target) left = mid + 1;
if (nums[mid] > target) right = mid - 1;

1. 返回值错误： 在循环结束后，mid 可能不代表目标插入位置，应返回 left，因为 left 是当前查找区间的起始位置。

---

修正代码

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return left;
}

感想

把能踩的坑全踩了一遍！！牛逼！！！🥳🥳🥳🥳