二分查找的边界设定

本文中下标均从$0$开始，len为数组的长度。

---

边界值left和right的初始值

例如在有序数组中查找指定值的下标时，可能的结果范围为$[0, len-1]$，因此初始化时应该使用：

int left = 0, right = len - 1;

但在查找插入位置问题（在有序数组中，找到插入指定值target的下标）中，边界的下标取值范围是$[0, len]$，即len也在取值范围中，因此初始化时应当设置：

int left = 0, right = len;

计算mid值

为了避免溢出，计算mid通常使用:

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

缩小边界

通常需要使用一个if...else...语句来改变边界，最方便清晰的方法，是将arr[mid] < target、arr[mid] == target和arr[mid] > target三种情况分别写出。

例如，在查找插入位置问题中，我们需要找到第一个小于等于target值的位置，这时可以考虑几个条件：

• arr[mid] < target: 这时左边界left应该在mid的右侧，因此应该取left = mid + 1
• arr[mid] > target: 这时右边界right应该在mid的左侧，因此应该取right = mid - 1
• arr[mid] == target: 这时mid左侧仍可能存在与target相等的元素，因此应使right = mid

if (arr[mid] < target) {
    left = mid + 1;
} else if (arr[mid] == target){
    right = mid;
} else {
    right = mid - 1;
}

循环的条件

通常将循环条件设为left < right，这样当循环退出时，可以保证left == right。

避免无限循环

while (left < right) {
    int mid = left + (right - left) / 2;
    if (condition1) {
        left = mid;
    }
    ...
}

在上述代码中，若数组中只有两个元素，即right == left + 1的情况下，条件condition1一直成立，这时mid == left恒成立，left一直得不到更新，始终满足while循环的条件，就会造成死循环。

因此可以通过下面的方式计算mid，以防出现死循环。

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

当出现死循环时，就应该分析一下数组里只有两个元素时，边界的收缩情况。

参考

1. https://leetcode.com/problems/binary-search/discuss/423162/Binary-Search-101