背景
这段时间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; } }
小结
1、以上二分搜索，对于mid是否溢出均未处理，如果给了数据集接近int的max，那么可以这么取mid = left + (right - left) / 2。
2、不等式二分搜索，属于常考的题目了，用于求取一些难解问题的最优值，这些难解的问题都有一个特点，问题可以转化成判定问题，这时候就可以二分的条件求值。
