ChatGPT，为啥写二分搜索容易死循环？

原创

Mark Sun

修改于 2023-03-30 23:38:02

5820

修改于 2023-03-30 23:38:02

背景

这段时间ChatGPT在码农界，引起了不小轰动，最热的话题中有一个与程序员息息相关，它会写代码那程序员是不是会集体下岗？刚好最近听说了这么一句话，“90%程序员都写不对二分搜索”，那就整个二分搜索最常见的问题考考ChatGPT。

了不起： 为什么写二分搜索容易死循环？

ChatGPT： 一个常见的原因是在二分搜索中没有正确处理边界情况，例如：

1、非递归实现中，循环终止条件可能不正确，导致死循环；

2、递归实现中，递归条件可能不正确，导致无限递归。

此外，当待搜索的数组不是有序时，也可能导致搜索结果不正确或死循环。如果你遇到了这个问题，可以仔细检查你的代码并尝试调试。可以使用打印语句或者调试器来寻找问题所在。同时，你也可以参考其他人的代码或者算法实现，再次检查你的思路是否正确。

了不起觉得，还算是一个中规中矩的答案，并没有十分惊艳，不过也讲到了关键所在就是条件处理。

随后让它给出一个二分搜索的代码，也与搜索引擎提供基本一致，没有系统的对二分问题做出分类，以下了不起总结的普通二分和不等式二分，几乎涵盖了所有的二分问题的方法论。

一、普通二分搜索

普通的二分搜索，就不再赘述，属于基本功了，现在的大多数算法面试也基本不再问。

1.1 编码实战

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

1.2 注意点

实数的二分就不用考虑所谓的mid+1和mid-1，因为index是整数是离散的，不是连续精确的，变更区间条件时出现死循环。

二、不等式二分搜索

2.1 三步走

1、写出二分的条件，需要满足的条件，包含mid的branch；

2、条件放到if，确定要求满足条件的mid的min（right = mid）或者max（left = mid）；

3、else left = mid + 1 或 right = mid - 1，后者需要在mid取值的时候补上+1。

2.2 注意点

mid取值补上1，是为了防止死循环，当left和right为5和6时，模拟想想。

前驱和后继和条件本身无关，与是否满足条件相关，如果是满足求min即是后继。

需要考虑如何表示无解？前驱left = -1，表示无解；后继right= n，表示无解。

2.3 编码实战

一段有序的数组但是有重复数组，搜索出目标数字的index区间。

public class _1_BinarySearch {
    public int[] searchRange(int[] nums, int target) {
        int leftBound = leftBound(nums, target);
        int rightBound = rightBound(nums, target);
        if (leftBound > rightBound) {
            return new int[]{-1, -1};
        }
        return new int[]{leftBound, rightBound};
    }
    // 前驱型往前找
    int rightBound(int[] nums, int target) {
        int left = -1;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right + 1) / 2;
            if (nums[mid] <= target) {
                left = mid; // max 向右扩张
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    // 后继型往后找
    int leftBound(int[] nums, int target) {
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) / 2;
            // 条件考虑了nums[mid]，即func(mid)的递增递减关系，需要满足这个条件
            if (nums[mid] >= target) {
                right = mid; // min 向左收缩
            } else {
                left = mid + 1;
            }
        }
        return left;
    }
}