【算法——二分查找】

理论基础：

程序员面试经典题，二分搜索一个区间，区间查找 (LeetCode 34)_哔哩哔哩_bilibili

手把手带你撕出正确的二分法 | 二分查找法 | 二分搜索法 | LeetCode：704. 二分查找_哔哩哔哩_bilibili

这个是红蓝法，很牛：二分查找为什么总是写错？_哔哩哔哩_bilibili

在二分查找中，计算中间位置使用mid = left + (right - left) / 2而不是mid = (left + right) / 2主要是为了避免整数溢出的问题。

此类型题目多样总结：

34. 在排序数组中查找元素的第一个和最后一个位置

因为二分无法查到起止位置；所以用两次二分，一次左边界，一次右边界；

会不会漏查问题：比如left左边会不会还有target

#include<iostream>
using namespace std;
#include<vector>
int main()
{vector<int>nums = { 2,2 };int target = 3;int l = -1, r = nums.size();while (l + 1 != r)    //找第一个target{int m = l + (r - l) / 2;if (nums[m] < target) l = m;else r = m;}if (r >= nums.size() || nums[r] != target) return -1;cout << "l:" << l << "  r:" << r << endl;      //r就是第一个targetl = -1; r = nums.size();while (l + 1 != r)  //找最后一个target{int m = l + (r - l) / 2;if (nums[m] <= target) l = m;else r = m;}cout << "l:" << l << "  r:" << r << endl;      //l就是最后一个targetreturn 0;
}

35. 搜索插入位置

#include<iostream>
using namespace std;
#include<vector>
int main()
{vector<int>nums = { 1,3,5,6 };int l = -1, r = nums.size();int target = 7;while (l + 1 != r){int m = l + (r - l) / 2;if (nums[m] >= target) r = m;   //核心else l = m;}cout << r;return 0;
}

69. x 的平方根