背景
这段时间ChatGPT在码农界，引起了不小轰动，最热的话题中有一个与程序员息息相关，它会写代码那程序员是不是会集体下岗？ 刚好最近听说了这么一句话，“90%程序员都写不对二分搜索”，那就整个二分搜索最常见的问题考考ChatGPT。
了不起： 为什么写二分搜索容易死循环？
ChatGPT： 一个常见的原因是在二分搜索中没有正确处理边界情况，例如：
1、非递归实现中，循环终止条件可能不正确，导致死循环；
2、递归实现中，递归条件可能不正确，导致无限递归。
此外，当待搜索的数组不是有序时，也可能导致搜索结果不正确或死循环。 如果你遇到了这个问题，可以仔细检查你的代码并尝试调试。可以使用打印语句或者调试器来寻找问题所在。同时，你也可以参考其他人的代码或者算法实现，再次检查你的思路是否正确。
了不起觉得，还算是一个中规中矩的答案，并没有十分惊艳，不过也讲到了关键所在就是条件处理。
随后让它给出一个二分搜索的代码，也与搜索引擎提供基本一致，没有系统的对二分问题做出分类，以下了不起总结的普通二分和不等式二分，几乎涵盖了所有的二分问题的方法论。
一、普通二分搜索
普通的二分搜索，就不再赘述，属于基本功了，现在的大多数算法面试也基本不再问。
1.1 编码实战
代码语言：javascript复制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区间。
代码语言：javascript复制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、不等式二分搜索，属于常考的题目了，用于求取一些难解问题的最优值，这些难解的问题都有一个特点，问题可以转化成判定问题，这时候就可以二分的条件求值。
