二分查找模版总结

二分查找是一种在 有序数组 中查找某一特定元素的搜索算法。元素集合有顺序，元素性质有分界点，二分法就可以用来求分界点，并不一定要求集合中元素是不重复的。

可以更快找到分界点

常规写法

int binarySearch(vector<int> &nums, int target) {
  int left = 0, right = nums.size() - 1; // 定义 target 在左闭右闭的区间里，[left, right]
  while (left <= right) { // 当 left==right，区间 [left, right] 依然有效，所以用 <=
    int mid = left + (right - left) / 2); // 防止溢出，结果等同于(left + right)/2
    if (nums[mid] > target) {
      right = mid - 1; // target 在左区间，所以更新为 [left, mid - 1]
    } else if (nums[mid] < target) {
      left = mid + 1; // target 在右区间，所以更新为 [mid + 1, right]
    } else {
      // nums[mid] == target
      return mid; // 数组中找到目标值，直接返回下标
    }
  }
  // 未找到目标值
  return -1;
}