力扣hot100——二分查找

35. 搜索插入位置

class Solution {
public:int searchInsert(vector<int>& a, int x) {if (a[0] > x) return 0;int l = 0, r = a.size() - 1;while (l < r) {int mid = (l + r + 1) / 2;if (a[mid] <= x) l = mid;else r = mid - 1;}if (a[l] == x) return l;else return l + 1;}
};

74. 搜索二维矩阵

class Solution {
public:bool searchMatrix(vector<vector<int>>& a, int target) {int n = a.size(), m = a[0].size();int l = 0, r = n * m - 1;int ans = 0;if (a[0][0] == target) ans = 1;auto check = [&](int x) -> bool {int i = x / m, j = x % m;if (a[i][j] == target) ans = 1;return a[i][j] <= target;};while (l < r) {int mid = (l + r + 1) / 2;if (check(mid)) l = mid;else r = mid - 1;}return ans;}
};

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

class Solution {
public:vector<int> searchRange(vector<int>& a, int target) {if (!a.size()) return { -1, -1 };int n = a.size();int l = 0, r = n - 1;vector<int> ans;while (l < r) {int mid = (l + r) / 2;if (a[mid] >= target) r = mid;else l = mid + 1;}if (a[l] == target) ans.push_back(l);l = 0, r = n - 1;while (l < r) {int mid = (l + r + 1) / 2;if (a[mid] <= target) l = mid;else r = mid - 1;}if (a[l] == target) ans.push_back(l);if (!ans.size()) return { -1, -1 };return ans;}
};    

33. 搜索旋转排序数组

class Solution {
public:int search(vector<int>& a, int target) {int n = a.size();if (target >= a[0]) {int l = 0, r = n - 1;while (l < r) {int mid = (l + r + 1) / 2;if (a[mid] <= target && a[mid] >= a[0]) l = mid;else r = mid - 1;}if (a[l] == target) {return l;}return -1;}else {int l = 0, r = n - 1;while (l < r) {int mid = (l + r + 1) / 2;if ((a[mid] <= target && a[mid] < a[0]) || a[mid] >= a[0]) l = mid;else r = mid - 1;}if (a[l] == target) {return l;}return -1;}}
};

二分，分类讨论，知道哪些情况需要缩小l或者r的范围 

153. 寻找旋转排序数组中的最小值

class Solution {
public:int findMin(vector<int>& a) {int n = a.size();if (a[0] < a[n - 1]) return a[0];int l = 0, r = n - 1;while (l < r) {int mid = (l + r) / 2;if (a[mid] < a[0]) r = mid;else l = mid + 1;}return a[l];}
};

1、讨论整个数组单调的情况
2、讨论有分段的情况，找到 < a[0]的第一个下标即可

 4. 寻找两个正序数组的中位数

class Solution {
public:double findMedianSortedArrays(vector<int>& a1, vector<int>& a2) {int n = a1.size() + a2.size();/*数组a1的前i个位置已经处理完，数组a2的前j个位置已经处理完，查找两数组后面部分的第k大*/auto find = [&](this auto&& find, vector<int>& a1, int i, vector<int>& a2, int j, int k)-> int {if (a1.size() - i > a2.size() - j) return find(a2, j, a1, i, k);/*a1不用找了*/if (i == a1.size()) return a2[j + k - 1];/*a1_{i + 1 - 1}, a2_{j + 1 - 1}*/if (k == 1) return min(a1[i], a2[j]);int idx1 = min((int)a1.size(), i + k / 2), idx2 = j + k - k / 2; // 减法避免整数溢出if (a1[idx1 - 1] < a2[idx2 - 1]) {return find(a1, idx1, a2, j, k - (idx1 - i));}elsereturn find(a1, i, a2, idx2, k - (idx2 - j));/*else if (a1[idx1 - 1] > a2[idx2 - 1]) {return find(a1, i, a2, idx2, k - (idx2 - j));}elsereturn a[idx1 - 1];};这么写，细节错误：原因是idx1可能为n，这样a2还没找完比如a1 = [3], a2 = [1, 2, 3, 4, 5]k = 6, idx1 = 1, idx2 = 3实际上第6大是5*/};if (n % 2 == 0) {return (find(a1, 0, a2, 0, n / 2) + find(a1, 0, a2, 0, n / 2 + 1) + 0.0) / 2;}else {return find(a1, 0, a2, 0, n / 2 + 1);}}
};

二分查找，每次每个数组分k/2（k表示第k大），这样缩小数组的范围和k的范围