二分搜索的模板和细节

最近做Leetcode题目总是遇到二分搜索的问题，本来觉得之前自己已经把这方面搞的很明白了，但是写起来还是各种别扭不痛快。问题主要集中于循环条件控制：是while(left <= right)还是while(left < right)，左右边界的缩小：是left = mid + 1还是left = mid，中值的计算问题：是mid = left + (right - left) / 2还是mid = left + (right - left + 1) / 2。今天的这篇文章就想把这些问题都说清楚。

首先我还是参考了网上labuladong写的文章的，感觉很受启发，其实很多算法都是有固定的模板的，不需要我们自己做什么创新。当然，这要能充分理解模板代码才行。

// 二分搜索的标准模板
private int binarySearch(int[] arr, int len, int target) {
  int left = 0;
  int right = len - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] < target) left = mid + 1;
    else if (arr[mid] > target) right = mid - 1;
    else if (arr[mid] == target) return mid; // find one, directly return
  }
  return -1; // can not find target
}

第一个问题，循环控制。这里如果说我们采用左右包含的区间设定，即[left, right]的话，那么循环的控制条件就应该是while(left <= right)，因为只有这样，才能说保证我们遍历了（有序数组中）所有的可能性。此时循环结束的条件是left = right + 1，最后一轮循环一定是left == right。如果说我们使用while(left < right)，那么就会错过数组中的一个元素[left, left]。

因为我个人是喜欢进行左右包含的区间分析的，所以左闭右开的设定我就不想涉及了。以后都应该按此模板来进行。

第二个问题，中值计算问题，这里一律使用mid = left + (right - left) / 2的操作，这个操作的意思等价于mid = (left + right) / 2，但是由于能够避免left,right的值过大造成加法溢出的问题，因此是一种更好的写法。之前自己总是纠结于这种中值的计算是在两个数相邻时取偏左侧的值（比如[3, 4]时取3），因而可以和边界缩小配合（比如说right = mid）防止无限循环。现在一律不要再进行这样复杂的思考了，中值计算问题一律使用这个定式。

第三个问题，左右边界的缩小，（由于我们规定了左右包含的区间设定）这里一律使用left = mid + 1或者right = mid - 1，再也不要出现left/right = mid的操作，可以保证循环正常结束。

对于一般的二分搜索要求，上面的模板代码已经完全可以解决。稍微复杂点的有下面两种变形情况：

左侧边界的二分搜索

如果存在target，那么就返回最左侧的那一个的索引值

如果不存在target，那么就返回（假如）插入target后target值所在的索引值

我们可以把左侧边界的二分搜索理解为：在原始的数组中，找到满足arr[index] >= target的最小index值

一个明显的例子就是，对于数组[1, 3, 3, 3, 4]，target = 3时正常的二分搜索返回index = 2（对应中间的那个3）；左侧边界的二分搜索要求返回index = 1（对应左侧的那个3）

对于正常的二分搜索，返回值的范围是[0, len - 1]；对于左侧边界的二分搜索，返回值的可能范围是[0, len]

// 左侧边界的二分搜索
private int binarySearch(int[] arr, int len, int target) {
  int left = 0;
  int right = len - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] < target) left = mid + 1;
    else if (arr[mid] > target) right = mid - 1;
    else if (arr[mid] == target) right = mid - 1; // find left bound
  }
  return left;
}

右侧边界的二分搜索

如果存在target，那么就返回最右侧的那一个的索引值

如果不存在target，那么就返回（假如）插入target后在target值之前的那个元素的索引值

我们可以把右侧边界的二分搜索理解为：在原始的数组中，找到满足arr[index] <= target的最大index值

对于正常的二分搜索，返回值的范围是[0, len - 1]；对于右侧边界的二分搜索，返回值的可能范围是[-1, len - 1]

// 右侧边界的二分搜索
private int binarySearch(int[] arr, int len, int target) {
  int left = 0;
  int right = len - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] < target) left = mid + 1;
    else if (arr[mid] > target) right = mid - 1;
    else if (arr[mid] == target) left = mid + 1; // find right bound
  }
  return right;
}

由此，我们可以获得任意条件下的二分搜索代码模板，比如说以获得arr[index] < target的最大index值，那么其代码（无脑）可以写作：

// the largest index that arr[index] < target 
private int binarySearch(int[] arr, int len, int target) {
  int left = 0;
  int right = len - 1;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (arr[mid] < target) left = mid + 1;
    else if (arr[mid] > target) right = mid - 1;
    else if (arr[mid] == target) ; // 待定1
  }
  return ; // 待定2
}

待定1：由于我们希望获得小于target的最大index值，所以当遇到arr[mid] == target时，理应继续往前找看看有没有更小的值，所以right = mid - 1

待定2：考虑到最后一轮循环的情况一定是left == right，此时分支代码告诉我们：[0, left - 1]的这些数一定满足arr[mid] < target；[right + 1, len - 1]的这些数一定满足arr[mid] >= target，也就是说，现在需要分析的范围被缩小到了只包含一个元素的[left, right]区间

此时如果说arr[mid] < target，那么就意味着[0, left]的数都满足arr[mid] < target，[right + 1, len - 1]的数都满足arr[mid] >= target，所以说此时的这个mid就是我们要找的最大index值，因为最后一次更新是left = mid + 1，也就是说，right变量保存了这个mid，应该返回right

如果说arr[mid] >= target，那么就意味着[0, left - 1]的数都满足arr[mid] < target，[right, len - 1]的数都满足arr[mid] >= target，所以说此时的这个mid - 1就是我们要找的最大index值，因为最后一次更新是right = mid - 1，也就是说，right变量保存了这个mid - 1，应该返回right