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