二分查找模板

一、查找精确值

从一个有序数组中找到一个符合要求的精确值（如猜数游戏）。如查找值为Key的元素下标，不存在返回-1。

//这里是left<=right。
//考虑这种情况：如果最后剩下A[i]和A[i+1]（这也是最容易导致导致死循环的情况)首先mid = i,
//如果A[mid] < key，那么left = mid+1 = i +1，如果是小于号，则A[i + 1]不会被检查，导致错误
int left = 1,right = n;
while(left <= right)
{
   //这里left和right代表的是数组下标，所有没有必要改写成mid = left + (right - left)/2;
  //因为当代表数组下标的时候，在数值越界之前，内存可能就已经越界了
  //如果left和right代表的是一个整数，就有必要使用后面一种写法防止整数越界
        int mid = (left + right) / 2;
    if(A[mid] == key)
      return mid;
    else if(A[mid] > key)//这里因为mid不可能是答案了，所以搜索范围都需要将mid排除
      right = mid - 1;
    else
      left = mid + 1;
}
return -1;

二、查找大于等于/大于key的第一个元素

这种通常题目描述为满足某种情况的最小的元素。

int left = 1,right = n;
while(left < right)
{
  //这里不需要加1。我们考虑如下的情况，最后只剩下A[i],A[i + 1]。
  //首先mid = i，如果A[mid] > key，那么right = left = i，跳出循环，如果A[mid] < key，left = right = i + 1跳出循环，所有不会死循环。
  int mid = (left + right) / 2;
  if(A[mid] > key)//如果要求大于等于可以加上等于，也可以是check(A[mid])
    right = mid;
  //因为找的是大于key的第一个元素，那么比A[mid]大的元素肯定不是第一个大于key的元素，因为A[mid]已经大于key了，所以把mid+1到后面的排除
  else
    left = mid + 1;
  //如果A[mid]小于key的话，那么A[mid]以及比A[mid]小的数都需要排除，因为他们都小于key。不可能是第一个大于等于key的元素，
}

三、查找小于等于/小于key的最后一个元素

这种通常题目描述为满足某种情况的最大的元素。如Leetcode69题，求sqrt(x)向下取整就是这种模板。

int left = 1, right = n;
while(left < right)
{
  //这里mid = (left + right + 1) / 2;
  //考虑如下一种情况，最后只剩下A[i],A[i + 1]，如果不加1，那么mid = i，如果A[mid] < key，执行更新操作后，left = mid，right = mid + 1，就会是死循环。
  //加上1后，mid = i + 1,如果A[mid] < key，那么left = right = mid + 1,跳出循环。如果A[mid] > key，left = mid = i，跳出循环。
  int mid = (left + right + 1) / 2;
  if(A[mid] < key)
    left = mid;//如果A[mid]小于key，说明比A[mid]更小的数肯定不是小于key的最大的元素了，所以要排除mid之前的所有元素
  else
    right = mid - 1;//如果A[mid]大于key，那么说明A[mid]以及比A[mid]还要大的数都不可能小于key，所以排除A[mid]及其之后的元素。
}

四、总结

最后两种情况的循环跳出条件是left<right，为什么不是小于等于呢？因为我们的区间变换思路是不断的舍去不可能是解的区间，最后只剩下一个数就是我们的解。而第一种情况就算最后只剩一个数也有可能不是解，所以需要使用小于等于。

• 查找精确值，循环条件是小于等于；查找满足情况的最大最小值，循环条件是小于。
• 查找满足条件的最大数，mid = (right + left + 1) / 2；查找满足条件的最小数，mid = (right + left)/2
• mid = left + (right - left) / 2，不是适用于所有的情况。
• 如果存在没有解的情况，比如从[1,2,3,4,5]找出大于等于6的第一个数，我们只需要将最后剩下的数单独进行一次判断就可以了。