LEETCODE HOT 100 二分查找 C‘s Log

二分查找也是最重要的就是明确自己变换的前提，也就是到底是哪个闭，哪个开，

转化成下面这句话可以这么思考：关键不在于区间里的元素具有什么性质，而是区间外面的元素具有什么性质，这个也是我在刷B站的灵神课的时候无意间看到的热一

35. 搜索插入位置 - 力扣（LeetCode）

这道题就是对区间到底开不开，以及对应的大小符号的一个判断，这里我们按照上面的逻辑和左闭右开区间来看：

1.区间有效，进入中点和左右指针的挪动，区间有效的意思是，这个区间存在，

左闭右开，那么左必须小于右，这个区间才成立

2.移动中点：也就是中点不在区间内，但是需要作为区间的最边边上的位置，移动左区间的时候，这个左指针是中点加一；移动右指针，这里中点本身就不包含在区间内，可以直接等于右

跳出循环的时候就是，左区间和右区间相遇了【这里不可能存在左区间到右区间的右边去的情况，结合上一轮循环进行判断】

那么此时返回的就是左指针【右指针也可以】

class Solution { int lower_bound2(vector<int>& nums, int target) { int left = 0, right = nums.size(); // 左闭右开区间 [left, right) // 区间不为空 while (left < right) { // nums[left-1] < target // nums[right] >= target int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid; } } return left; } public: int searchInsert(vector<int>& nums, int target) { return lower_bound2(nums, target); } };

在针对左闭右闭区间的这里为什么不能返回right，而必须返回left

• 返回left：因为left是“追赶者”，它一直试图往右找更大的，直到越过边界。

• 不返回right：因为right是“排斥者”，它一直在把不符合条件（ << target）的数排除在左边。循环结束时，它正好停在“最后一个不符合条件的数”上

• class Solution { int lower_bound(vector<int>& nums, int target) { int left = 0, right = (int) nums.size() - 1; // 闭区间 [left, right] while (left <= right) { // 区间不为空 // nums[left-1] < target // nums[right+1] >= target int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else { right = mid - 1; } } return left; } public: int searchInsert(vector<int>& nums, int target) { return lower_bound(nums, target); } };

74. 搜索二维矩阵 - 力扣（LeetCode）

矩阵的每一行是递增的，且每行的第一个数大于前一行的最后一个数，如果把矩阵每一行拼在一起，我们可以得到一个递增数组【闭区间写法】

class Solution { public: bool searchMatrix(vector<vector<int>>& matrix, int target) { int m = matrix.size(), n = matrix[0].size(); int left = 0, right = m * n - 1; // left <= right区间有效 while (left <= right) { int mid = left + (right - left) / 2; // 将一维坐标映射回二维坐标 // 假设 n 是列数 int x = matrix[mid / n][mid % n]; if (x == target) { return true; // 找到目标值 } else if (x < target) { left = mid + 1; } else { right = mid - 1; } } return false; } };

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

“非递减顺序排列”的意思是：后面的数要么比前面的大，要么和前面的相等

依旧左闭右闭

class Solution { // lower_bound 返回最小的满足 nums[i] >= target 的下标 i // 如果数组为空，或者所有数都 < target，则返回 nums.size() // 要求 nums 是非递减的，即 nums[i] <= nums[i + 1] int lower_bound(vector<int>& nums, int target) { int left = 0, right = (int) nums.size() - 1; // 闭区间 while (left <= right) { // 不为空 // nums[left-1] < target // nums[right+1] >= target int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid - 1; left = mid + 1; } } // left = right+1 // nums[left-1] < target 而 nums[left] = nums[right+1] >= target // left 就是第一个 >= target 的元素下标 return left; } public: vector<int> searchRange(vector<int>& nums, int target) { int start = lower_bound(nums, target); if (start == nums.size() || nums[start] != target) { return {-1, -1}; //没有 target } int end = lower_bound(nums, target + 1) - 1; return {start, end}; } };

33. 搜索旋转排序数组 - 力扣（LeetCode）

这道题的逻辑就是下面一道题加上在有序数组中找到目标值，两个结合起来的逻辑

重点是判断各种返回的值，也就是具体什么时候反馈什么样的值来确定目标

这里每个值都独一无二，也就是说不存在重复的值

为什么返回left 还是上面最粗的字表述的，left和right在左闭右闭的关系

class Solution { int findMinIndex(vector<int>& nums) { int left = 0; int right = nums.size() - 1; // 区间不为空，也就是等到left=right时这个值就是最小值 while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] > nums[right]) { // 中间 > 右边 // 说明 mid 还在“大数段”，最小点点一定在 mid 的右侧 left = mid + 1; } else { // 中间 <= 右边 // 说明 [mid, right] 这一段是有序的 // 断点可能是 mid，也可能在 mid 左侧 right = mid; } } return left; // 此时 left == right } int lower_bound(vector<int>& nums, int left, int right, int target) { while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] >= target) { right = mid - 1; // 范围缩小到 [left, mid-1] } else { left = mid + 1; // 范围缩小到 [mid+1, right] } } // 循环结束时 left == right + 1 // left 指向的是第一个 >= target 的位置 return left < nums.size() && nums[left] == target ? left : -1; } public: int search(vector<int>& nums, int target) { int i = findMinIndex(nums); // i 是最小值的下标 if (target > nums.back()) { // 目标值比数组的最后一个值大，说明在前半段数组更大 // i=0，说明更大的段没了 if (i == 0) return -1; return lower_bound(nums, 0, i - 1, target); } else { //target 在第二段 [i, n-1] return lower_bound(nums, i, nums.size() - 1, target); } } };

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

这个旋转几次应该无所谓的，反正最后得到一个一段加一段有顺序的数组进行判断就可以了，

通过mid与左右点的大小判断来判断最小值可能出现在当前数组的左半段还是右半段

class Solution { public: int findMin(vector<int>& nums) { int left = 0; int right = nums.size()-1; while (left<right){ int mid = left + (right-left)/2; if(nums[mid]>nums[right]){ // mid 在左半段，最小值在右边 left = mid + 1; } else{ // mid 在右半段，最小值是 mid 或者在左边 right = mid; // mid本身有可能就是答案 } } // 结束时 left == right return nums[left]; } };

4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

left 和 right 是在数组 a 上不断收缩的搜索边界，用来锁定最佳切点 i，而 i 和 j 则是最终落在两个数组上的分割刻度，用来划定左右阵营并确定中位数的位置，没有好的办法，只能自己用手画去理解

为什么是a[i-1]

左半边的最大值

• 这i个元素的下标分别是：0, 1, ..., i-1；
• 那么这堆元素里最后一个（最大的那个），自然就是下标为i-1的元素。

同理，a右边的最小值（即第i+1个元素），其下标就是i（即a[i]）

“闭区间”体现在while (left <= right)和right = m上。

这意味着我们的切割线i可以取到边界值：

• i可以是 0：表示a一个元素都不贡献给左边。此时a[i-1]即a[-1]，这就是为什么要用INT_MIN来保护的原因。
• i可以是 m：表示a把所有元素都贡献给左边。此时a[i]即a[m]，这就是为什么要用INT_MAX来保护的原因。

总体来说就是，按照灵神的思路，上面当作数组a,下面当作数组b，不断地去改变二分的结构

class Solution { public: double findMedianSortedArrays(vector<int>& a, vector<int>& b) { // a 是较短的数组 if (a.size() > b.size()) { swap(a, b); } int m = a.size(), n = b.size(); int left = 0; int right = m; // i 可以取到 m int totalLeft = (m + n + 1) / 2; // 左半边总共需要的元素个数 while (left <= right) { //不为空 int i = left + (right - left) / 2; // a 数组左边有 i 个元素 int j = totalLeft - i; // b 数组左边有 j 个元素，i+j=总长度平均分的一半 // 边界保护（防止 i=0 或 j=n 时越界） int aLeftMax = (i == 0) ? INT_MIN : a[i - 1]; int bRightMin = (j == n) ? INT_MAX : b[j]; // a[i-1] 是 a 左边的最大值，b[j] 是 b 右边的最小值 // 如果 a 左边的最大值 > b 右边的最小值，说明 a 分给左边的太多了 if (aLeftMax > bRightMin) { right = i - 1; // i 太大了，往左找 } // 如果 a 左边的最大值 <= b 右边的最小值，说明 i 合法或者还可以更大，往右找更大的 i else if (aLeftMax <= bRightMin) { left = i + 1; } } // 循环结束时，left > right // right 是最终的切割位置 ( i) // left 是 right + 1 int i = right; int j = totalLeft - i; // 获取四个关键值，注意处理越界 (INT_MIN / INT_MAX) int aLeftMax = (i == 0) ? INT_MIN : a[i - 1]; // a 左边最大 int bLeftMax = (j == 0) ? INT_MIN : b[j - 1]; // b 左边最大 int aRightMin = (i == m) ? INT_MAX : a[i]; // a 右边最小 int bRightMin = (j == n) ? INT_MAX : b[j]; // b 右边最小 // 计算中位数 if ((m + n) % 2 == 1) { // 奇数：取左边的最大值 return max(aLeftMax, bLeftMax); } else { // 偶数：取 (左边最大 + 右边最小) / 2.0 return (max(aLeftMax, bLeftMax) + min(aRightMin, bRightMin)) / 2.0; } } };