Review binary search

33. 搜索旋转排序数组 – 力扣（LeetCode）
81. 搜索旋转排序数组 II – 力扣（LeetCode）
153. 寻找旋转排序数组中的最小值 – 力扣（LeetCode）
154. 寻找旋转排序数组中的最小值 II – 力扣（LeetCode）
34. 在排序数组中查找元素的第一个和最后一个位置 – 力扣（LeetCode）
35. 搜索插入位置 – 力扣（LeetCode）
69. x 的平方根 – 力扣（LeetCode）
704. 二分查找 – 力扣（LeetCode）

整数二分查找模板

基本

int binary_search(vector<int> nums, int target) {
  int low = 0, high = nums.size() - 1;
  while (low <= high) {
    // avoid int overflow
    int mid = low + (high - low) / 2;
    if (nums[mid] == target) {
      return mid;
    } else if (nums[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

下界

// 寻找下界, 即大于等于target的第一个元素位置
int lower_bound(vector<int> nums, int target) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    int mid = low + (high - mid) / 2;
    if (nums[mid] >= target) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }
  // nums.size() > 0, 防止nums[low] underflow
  return nums.size() > 0 && nums[low] == target ? low : -1;
}

上界

// 寻找上界, 即小于等于target的最后一个元素位置
// 与cpp标准库的upper_bound(...)含义不同
int upper_bound(vector<int> nums, int target) {
  int low = 0, high = nums.size() - 1;
  while (low < high) {
    // 避免当high=2147483647,  加一overflow
    int mid = low + (high - low + (long long)1) / 2;
    if (nums[mid] <= target) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  return nums.size() > 0 && nums[low] == target ? low : -1;
}

样例

// -1表示不存在此元素
int main() {
  int target1 = 5, target2 = 6;
  vector<int> nums = {1, 4, 5, 5, 5, 5, 5, 7, 8};
  // 输出4
  cout << binary_search(nums, target1) << endl;
  // 输出2
  cout << lower_bound(nums, target1) << endl;
  // 输出6
  cout << upper_bound(nums, target1) << endl;
  // 输出-1
  cout << binary_search(nums, target2) << endl;
  // 输出-1
  cout << lower_bound(nums, target2) << endl;
  // 输出-1
  cout << upper_bound(nums, target2) << endl;
  return 0;
}

什么的题用什么样的模板

low 和 high 的取值与题意有关，当给定非降序数组以及 target，搜索 target 是否在数组内，low 和 high由数组长度决定，即搜索区间[0, nums.size() - 1]，当题意是搜索 target 并当 target 不在数组时搜索 target 应该插入的位置，插入位置即数组中大于等于 target 的第一个元素位置，此时搜索区间为[0, nums.size()]，

对于应用第二第三模板中return语句的判断条件的解释，由于是通过逐渐缩小区间来得到答案，此时需要根据题意来决定是否需要多余的校验，比如对于153，154搜索旋转排序数组中的最小值，根据题意即可判断出肯定存在最小值，所以不需要额外的nums[low] == target，但是对于34题，确定 target 在排序数组中查找元素的第一个和最后一个位置，需要额外的校验，因为target未必在数组内，此题使用模板一更好处理。

旋转数组

33/81

33题

81

对于33，81思考以上两幅图

153/154

浮点数二分

sqrt(float)

todo

参考资料

1. 二分查找有几种写法？它们的区别是什么？ – Jason Li的回答 – 知乎 https://www.zhihu.com/question/36132386/answer/530313852
2. https://ai.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html
3. https://www.acwing.com/blog/content/277/