二分查找

二分查找可以是计算机领域最著名的算法了，它针对有序序列可以极高的提升查找效率。但是要写好二分查找可是确实不容易的。即使是大神也发出了下面的感慨

1	Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky…

思想大家都知道，具体实现细节全是坑，一不留神就掉里面了。这里我们详细的对坑点进行分析与总结。

二分查找的最基础格式

首先我们先来看二分查找的最基础模版，这里我们拿leetcode的模板.

int binarySearch(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size() - 1;   // 1
  while(left <= right){   // 2
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;  // 3
    if(nums[mid] == target){ return mid; }
    else if(nums[mid] < target) { left = mid + 1; }  //4
    else { right = mid - 1; } // 5
  }

  // End Condition: left > right
  return -1;
}

下面我们来看上面的代码的坑点

left和right的取值，这里我们取的是全闭区间【left，right】，也就是我们可以取到left和right的值。
while语句中控制迭代终止变量(left <= right)，因为上面的区间是全闭区间，所以left是可以等于right的，所以只有在left 〉right的时候，才能使迭代终止。如果是while(left < right) 那么在left == right的时候就终止了，那么这个相等的值就被漏掉了。
求取mid的值，这一个实际上是一个越界保护，可能会坑新手
更新left和right的值，这个跟第一步取的全闭区间也是有关系的，当我们的mid不符合条件的时候，表明我们的mid是已经被用过了的。而我们使用的是全闭区间，也就是这些值都是可以被取到使用的，因此我们新的二分区间，应该是【left， mid - 1】活着【mid + 1， right】

当我们找不到的符合条件的target的时候，就直接return -1就好了。

经过上面的分析，我们可以看出上面的算法模板最本质的就是要抓住一点，二分查找区间是什么，如果是全闭区间【left，right】，就要根据全闭区间的特征来具体的设置迭代终止条件以及左右区间的更新。

leetcode的如下的几个习题都可以用这个模板直接解决
https://leetcode-cn.com/problems/sqrtx/
https://leetcode-cn.com/problems/guess-number-higher-or-lower/

基础格式有啥问题

按照上面的逻辑看二分查找很清晰阿，为什么大神们都会说它tricky呢，还是surpringly tricky呢？主要原因还是在于它存在着变种，各种条件混在一起，就会把水给搅的浑浑的。
我们看上面的模板会有一个什么问题呢？假设我们有下面的一个有序数组[1,2,2,2,2,2,3,4,5]，我们要查找第一个2出现的位置。因为这是一个有序的数组，所以直接上二分查找，用上面的框架得到的结果是索引4的位置，但这并不是第一个出现2的位置。那么我们可以怎么办呢？我们可以以这个为起始点，向左继续查找，直到查找到第一个2的出现，那么这就需要做两次2分查找。那么有没有更好的方式呢？下面就是二分查找的寻找左侧边界的模板

寻找左侧边界的模板

int leftBound(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size();   // 1
  while(left < right){   // 2
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;  // 3
    if(nums[mid] == target){ right = mid}
    else if(nums[mid] < target) { left = mid + 1; }  //4
    else { right = mid; } // 5
  }

  // End Condition: left > right
  return left;  // 6
}

下面我们来看细节：

取值区间 [left, right)，也就意味着是取不到right的值的。
所以我们的迭代范围会自然而然的为left < right
也就因此对于left，我们是要用left = mid + 1更新。因为mid已经用过了，所以left = mid + 1.而right的值我们取不到，所以用right = mid更新即可。
因为我们需要查询左侧边界，所以当nums[mid] == target的时候，不是返回，而是缩小我们的右侧边界，缩小继续遍历的空间，以便让程序进行查找。
最后我们return left; 这里left一定就是最左边的边界。这是为什么呢？因为当迭代停止的时候，一定是left == right的时候，这个时候返回left和right是一样的，但是我们的right是一直在向左边界逼近的，所以返回left也是一样的。

leetcode的如下的几个习题都可以用这个模板直接解决
https://leetcode-cn.com/problems/first-bad-version/

寻找右侧边界的模板

寻找右侧边界的模板跟寻找左侧边界的模板的原理是一样的，如下所示：

int rightBound(vector<int>& nums, int target){
  if(nums.size() == 0)
    return -1;

  int left = 0, right = nums.size();   // 1
  while(left < right){   // 2
    // Prevent (left + right) overflow
    int mid = left + (right - left) / 2;  // 3
    if(nums[mid] == target){ left = mid + 1; }
    else if(nums[mid] < target) { left = mid + 1; }  //4
    else { right = mid; } // 5
  }

  // End Condition: left > right
  return left - 1;
}

同样的，下面我们来看细节：

取值区间 [left, right)，也就意味着是取不到right的值的。
所以我们的迭代范围会自然而然的为left < right
也就因此对于left，我们是要用left = mid + 1更新。因为mid已经用过了，所以left = mid + 1.而right的值我们取不到，所以用right = mid更新即可。
因为我们需要查询右侧边界，所以当nums[mid] == target的时候，不是直接停止，而是右缩左侧边界，缩小继续遍历的空间，以便让程序进行查找。
最后我们return left - 1; 因为当迭代停止的时候，一定是left == right的时候，这个时候返回left和right是一样的，但是我们的right是开区间，所以返回left - 1，或者范围right - 1也是一样的。

leetcode的如下的几个习题都可以用这个模板直接解决
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/