参考：二分查找细节详解（我写了首诗，让你闭着眼睛也能写对二分搜索）

注：计算 **mid** 位置时，应该使用 mid = left + (right - left) / 2 而不是 mid = (left + right) / 2，以避免 left 和 right 相加溢出

0、二分查找框架

int binarySearch(vector<int>& nums, int target)
{
    int left = 0;
    int right = ...;
    while(...)
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)
        {
            ...
        }
        else if(nums[mid] < target)
        {
            left = ...;
        }
        else if(nums[mid] > target)
        {
            right = ...;
        }
    }
    return ...;
}

二分查找统一框架模板：

只需改动两处（如下的变化一、变化二）

int binarySearch(vector<int>& nums, int target)
{
  int left = 0;
  int right = nums.size() - 1;    // 搜索区间右侧也是闭区间，因此 right = len - 1
  // 搜索区间为 [left, right]，当 left>right 时搜索空间变为空，结束搜索
  while(left <= right)
  {
      int mid = left + (right - left) / 2;    // 防止溢出
      if(nums[mid] == target)
      {
          // // 变化一：
          // // case 1. 如果是查找 target，则找到直接返回
          // return mid;
          // // case 2. 如果是查找 target 左边界，则收缩 right
          // right = mid - 1;
          // // case 3. 如果是查找 target 右边界，则收缩 left
          // left = mid + 1;
      }
      else if(nums[mid] < target)
          left = mid + 1;
      else if(nums[mid] > target)
          right = mid - 1;
  }
  // // 变化二：
  // // case 1. 如果是查找 target，则未找到直接返回 -1
  // return -1;
  // // case 2. 如果是查找 target 左边界，则要检查 left 越界的情况
  // if(left >= nums.size() || nums[left] != target)
  //     return -1;
  // return left;
  // // case 3. 如果是查找 target 右边界，则要检查 right 越界的情况
  // if(right < 0 || nums[rigt] != target)
  //     return -1;
  // return right;
}

注：对于 case 2 和 case 3，即查找 target 左边界 or 右边界的情形，如果数组 nums 中不存在 target，那么最终 left 指向 > target 的第一个元素，right 指向 < target 的第一个元素

1、寻找 target

1.0 寻找 target (最基本的二分查找)

给定一个升序数组，给定一个待查找的目标值 target，要求返回其下标

解法：
定义在左闭右闭区间 [left, right] 搜索 target，如果查找范围不为空，即 left <= right，则迭代搜索：

计算 mid 下标
如果 mid 的值就是 target，即找到目标值，停止搜索
如果 mid 的值大于 target，则说明目标值在 mid 左边，令右边界 **right = mid - 1**，以缩小查找范围

如果 mid 的值小于 target，则说明目标值在 mid 右边，令左边界 **left = mid + 1**，以缩小查找范围

int binarySearch(vector<int>& nums, int target) {
  int left = 0;
  int right = nums.size() - 1;
  // 循环条件为 left<=right，即，当 left>right 时结束搜索
  // 因为搜索区间两端都是闭区间[left,right]，因此 left>right 时区间为空，停止搜索
  while(left <= right)            // 搜索区间为 [left, right]
  {
      int mid = left + (right - left) / 2;
      if(nums[mid] == target)        // 找到目标值，停止搜索
          return mid;
      // 未找到目标值，缩小搜索区间
      // 因为 mid 确定不符合要求了，所以搜索区间中要去除 mid 本身
      if(nums[mid] > target)        // 搜索区间变为 [left, mid-1]
          right = mid - 1;
      else if(nums[mid] < target)    // 搜索区间变为 [mid+1, right]
          left = mid + 1;            
  }
  return -1;
}

1.1 寻找 target 的左边界

如果数组是 [1, 3, 4, 4, 4, 4, 6]，target = 4，用前面的方法找到的 target 的下标为 3，并不是左边界下标 2，那么如何寻找左边界？有一个和之前方法统一的框架：

int binarySearchLeftBoundary(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right)            // 搜索区间为 [left, right]
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)        // 找到目标值，收缩右边界（区别 1）
            right = mid - 1;
        // 未找到目标值，缩小搜索区间
        // 因为 mid 缺点不符合要求了，所以搜索区间中要去除 mid 本身
        else if(nums[mid] > target)    // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        else if(nums[mid] < target)    // 搜索区间变为 [mid+1, right]
            left = mid + 1;            
    }
    // 区别 2
    // 检查 left 出界情况(当 target 比 nums 中所有元素都大时，left 最终会越界)
    // 数组中不存在 target 时，最终 left 指向的是比 target 大的第一个元素
    // 最终 right 则指向比 target 小的第一个元素 
    if(left >= nums.size() || nums[left] != target)
        return -1;
    return left;
}

1.2 寻找 target 的右边界

如果数组是 [1, 3, 4, 4, 4, 4, 6]，target = 4，那么 target 的右边界下标是 5 。和之前方法统一的框架如下：

int binarySearchRightBoundary(vector<int>& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while(left <= right)            // 搜索区间为 [left, right]
    {
        int mid = left + (right - left) / 2;
        if(nums[mid] == target)        // 找到目标值，收缩左边界（区别 1）
            left = mid + 1;
        // 未找到目标值，缩小搜索区间
        // 因为 mid 缺点不符合要求了，所以搜索区间中要去除 mid 本身
        else if(nums[mid] > target)    // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        else if(nums[mid] < target)    // 搜索区间变为 [mid+1, right]
            left = mid + 1;            
    }
    // 区别 2
    // 检查 right 出界情况(当 target 比 nums 中所有元素都小时，right 最终会越界)
    // 数组中不存在 target 时，最终 left 指向的是比 target 大的第一个元素
    // 最终 right 则指向比 target 小的第一个元素 
    if(right < 0 || nums[right] != target)
        return -1;
    return right;
}

1.3 查找比 target 小的最大的位置

设数组 nums 为 [2, 4, 5, 7, 10]，target = 6，查找比 target 小的最大的位置，就是 2，因为 nums[2] = 5 < 6，且 nums[3] = 7 > 6

统一框架写法：先二分寻找 targe 的左边界，

如果 nums 中存在 target，则最终找到的左边界 left 再减一，就是比 target 小的最大位置

如果 nums 中不存在 target，则最终的 right 就是比 target 小的最大位置

int search(vector<int>& nums, int target) {
  int left = 0;
  int right = nums.size() - 1;
  while(left <= right)            // 搜索区间为 [left, right]
  {
      int mid = left + (right - left) / 2;
      if(nums[mid] == target)        // 找到目标值，收缩右边界
          right = mid - 1;
      // 未找到目标值，缩小搜索区间
      // 因为 mid 缺点不符合要求了，所以搜索区间中要去除 mid 本身
      else if(nums[mid] > target)    // 搜索区间变为 [left, mid-1]
          right = mid - 1;
      else if(nums[mid] < target)    // 搜索区间变为 [mid+1, right]
          left = mid + 1;            
  }

  // 检查 left 出界情况(当 target 比 nums 中所有元素都大时，left 最终会越界)
  // 数组中不存在 target 时，最终 left 指向的是比 target 大的第一个元素
  // 最终 right 则指向比 target 小的第一个元素 
  if(left >= nums.size() || nums[left] != target)
      return right;
  return left - 1;
}

另一种写法：

int search(vector<int>& nums, int target) {
  int left = 0;
  int right = nums.size() - 1;
  int pos = -1;    // 带查找的比 target 小的最大的位置，初始化为 -1，代表不存在比 target 小的数
  while(left <= right)            // 搜索区间为 [left, right]
  {
      int mid = left + (right - left) / 2;

      if(nums[mid] < target)        // 搜索区间变为 [mid+1, right]
      {
          pos = mid;                // 更新 pos
          left = mid + 1;
      }
      else                        // 搜索区间变为 [left, mid-1]
          right = mid - 1;            
  }
  return pos;
}

例 1：最长递增子序列

[中等] 300. 最长递增子序列

2、寻找最值

给定一个并非完全有序的数组（eg. 旋转数组），寻找最值

解法：
如果查找范围大于一个点，则迭代搜索，直至查找范围只剩下一个点：

计算 mid 下标
如果 mid 的值满足某种条件，令右边界 right = mid（注意包含 mid 本身，mid 不减 1），以缩小查找范围

否则，令左边界 left = mid + 1，以缩小查找范围

int search(vector<int>& nums) {
  int left = 0;
  int right = nums.size() - 1;
  // 循环，直到搜索区间只剩下一个点，就是最值
  while(left < right)                // 搜索区间为 [left, right]
  {
      int mid = left + (right - left) / 2;

      if(nums[mid] 满足某种条件)    // 搜索区间变为 [left, mid]（区别，包含 mid）
          right = mid;
      else                        // 搜索区间变为 [mid+1, right]
          left = mid + 1;            
  }
  return left
}

例 1：旋转数组的最小数字

[容易] 剑指 Offer 11. 旋转数组的最小数字

class Solution {
public:
    int minArray(vector<int>& numbers) {
        int left = 0;
        int right = numbers.size() - 1;

        // 特殊情况：如果最左边元素小于最右边元素，说明数组未旋转，仍是递增的，直接返回最左边元素
        // 注意：由于数组中可以包含重复元素，因此如果最左边元素等于最右边元素，无法判断数组是否递增
        if(numbers[left] < numbers[right])
            return numbers[left];

        // 二分查找
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            // case1：numbers[mid] < numbers[right]，说明 numbers[mid] 是最小值右侧（含最小值本身）的元素
            // 因此忽略二分查找的右半区间，到左半区间继续查找
            // 因为 numbers[mid] 本身可能就是最小值，因此令 right=mid，而不是 mid-1
            if(numbers[mid] < numbers[right])
                right = mid;
            // case2：numbers[mid] > numbers[right]，说明 numbers[mid] 是最小值左侧的元素（肯定不含最小值本身）
            // 因此忽略二分查找的左半区间，到右半区间继续查找
            // 因为 numbers[mid] 本身不可能就是最小值，因此令 left=mid+1
            else if(numbers[mid] > numbers[right])
                left = mid + 1;
            // case3：numbers[mid] == numbers[right]，无法判定 numbers[mid] 在最小值左侧还是右侧
            // 但是因为 numbers[mid] == numbers[right]，因此 numbers[right] 无论是不是最小值，都有重复值
            // 因此可以忽略 numbers[right]
            else
                --right;
        }
        return numbers[left];
    }
};

例 2：寻找峰值

[中等] 162. 寻找峰值

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        int left = 0;
        int right = nums.size() - 1;
        while(left < right)
        {
            int mid = left + (right - left) / 2;
            // 如果 mid 处于一段下降序列，则峰值在 mid 左边（含 mid 本身）
            if(mid + 1 == nums.size() || nums[mid] > nums[mid + 1])
                right = mid;
            else    /// 否则，峰值在 mid 右边
                left = mid + 1;
        }
        return left;
    }
};

3、其它

[困难] 4. 寻找两个正序数组的中位数
 [容易] 69. x 的平方根

二分查找