关于算法:二分查找的边界设定

边界值 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…