目录
前言
🎂搜索插入位置
🌼搜索二维矩阵
🌼排序数组元素第一和最后一个位置
🌼旋转排序数组
💪旋转排序数组中的最小值
💪两个正序数组的中位数
前言
二分算法学习_时间超限ac:0%-CSDN博客
🎂搜索插入位置
35. 搜索插入位置 - 力扣（LeetCode）
直接套博客里的万能模板不太行，万能模板只能处理下取整死循环的问题，但是本题：
目标值 target 不一定在数组里
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = (l + r) >> 1;
if (target > nums[m])
l = m + 1;
else if (target < nums[m])
r = m - 1;
else {
l = m;
break;
}
}
// 因为 l<=r 退出循环后, r 必然位于插入位置
return l;
}
};🌼搜索二维矩阵
74. 搜索二维矩阵 - 力扣（LeetCode）
1）别混淆 mid 和 m，此处 m 是 m 行，mid 才是中间值
2）对第 3 种情况，target == matrix[][]，进行处理
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int l = 0, r = m*n - 1; // 二维转一维
while (l < r) {
int mid = (l + r + 1) >> 1;
if (target > matrix[mid/n][mid%n]) // 一维转二维
l = mid;
else if (target < matrix[mid/n][mid%n])
r = mid - 1;
else {
l = mid;
break;
}
}
return matrix[l/n][l%n] == target;
}
};🌼排序数组元素第一和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
1）利用 while (l <= r) { ... l = m + 1 ... r = m - 1 }; 左闭右闭区间
退出循环时，l 的位置就是 >= target 的最小的数
r == l - 1
2）只需求出第一个位置，即可取巧得到最后一个位置，现在有二分函数 lowerbound(nums, target) 得到第一个位置，最后一个位置即 lowerbound(nums, target + 1) - 1
3）奇数个元素，m = (l + r) / 2，取到中间的元素；偶数个元素，因为整数默认下取整，会取中间两个元素左边那个
坑：
1）不要用 >> 1，要用 / 2，不知道力扣是不是不支持位移运算符（>> 1 会超出时间限制）
2）如果想要从 r = m - 1 开始，那么最后应该 return r; r 此时位于最后一个位置（详情看代码 2）（用例1模拟一下）
代码 1
class Solution {
public:
// >= target 的最小的数的位置
int lowerbound(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (target > nums[m])
l = m + 1;
else
r = m - 1;
}
return l; // 第一个位置
}
vector<int> searchRange(vector<int>& nums, int target) {
int start = lowerbound(nums, target);
if (start >= nums.size() || nums[start] != target)
return {-1, -1};
int end = lowerbound(nums, target + 1) - 1;
return {start, end};
}
};
代码 2
class Solution {
public:
// >= target 的最小的数的位置
int lowerbound(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (target < nums[m])
r = m - 1;
else
l = m + 1;
}
return r; // 最后一个位置
}
vector<int> searchRange(vector<int>& nums, int target) {
int end = lowerbound(nums, target);
if (end < 0 || nums[end] != target)
return {-1, -1};
int start = lowerbound(nums, target - 1) + 1;
return {start, end};
}
};
🌼旋转排序数组
33. 搜索旋转排序数组 - 力扣（LeetCode）
1）二分时，套 while (l <= r) 的模板，mid 位于中间 OR 中间偏左位置
此时，[l, mid] OR [mid + 1, r]，至少一个区间是有序的，所以对左右区间的有序分类讨论
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = nums.size();
int l = 0, r = n - 1;
// 二分找到 k 的位置
while (l <= r) {
int mid = (l + r) / 2;
// target 位于 mid
if (nums[mid] == target)
return mid;
// 左边有序
else if (nums[l] <= nums[mid]) {
// target 位于左边（不包括 mid）
if (nums[l] <= target && target < nums[mid])
r = mid - 1;
else
l = mid + 1;
}
// 右边有序
else {
// target 位于右边（不包括 mid）
if (nums[mid] < target && target <= nums[r])
l = mid + 1;
else
r = mid - 1;
}
}
return -1; // 未找到
}
};💪旋转排序数组中的最小值
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
上一题是找目标值，本题是找最小值（都满足部分有序）
本题每次旋转，将最后一个值提取到最前面
可以画几个例子多验证一下：2 0 1，1 2 0，3 4 5 2，5 2 3 4
最小值处于断崖的第一个位置，显而易见，肯定位于无序一边
所以每次压缩有序部分，到无序部分找，注意结合例子处理边界
class Solution {
public:
int findMin(vector<int>& nums) {
int n = nums.size();
int l = 0, r = n - 1;
while (l <= r) { // l < r 也行
// 单调升序
if (nums[l] <= nums[r]) // 用 = 防止单个元素时死循环
return nums[l];
int m = (l + r) / 2;
// 左边有序
if (nums[m] >= nums[l]) // 用 = 防止 r 跳过最小值
l = m + 1; // 去右边找
else
r = m; // 不用 m-1 防止跳过最小值
}
return nums[l];
}
};💪两个正序数组的中位数
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
结合这篇博客理解一下，用删除（淘汰）的思路
寻找两个正序数组的中位数（292） | 小浩算法 (geekxh.com)辅助数组 findKth(nums1, i, nums2, j, k)，i, j 是两个数组起始索引，第 k 大元素
如果第一个数组起始位置 i + 2/k - 1 的值 < 第二个数组起始位置 j + 2/k - 1 的值
那么就淘汰掉第一个数组前 2/k 个元素，反之淘汰另一个数组前 2/k 个元素
直到 k == 1，此时比较两个数组起始第 1 个元素大小即可
；
或者一个数组为空（即 i >= nums1.size() 或 j >= nums2.size()）
时间 O(log( max(m, n) ))
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size(), m = nums2.size();
int left = (n + m + 1) / 2, right = (n + m + 2) / 2; // 中间值索引 left 和 right
return (findKth(nums1, 0, nums2, 0, left) + findKth(nums1, 0, nums2, 0, right)) / 2.0;
}
// nums1 起始索引 i, nums2 起始索引 j, 返回合并数组 第 k 个元素（1开始算）
int findKth(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
if (i >= nums1.size()) // nums1 空数组
return nums2[j + k - 1];
if (j >= nums2.size()) // nums2 空数组
return nums1[i + k - 1];
if (k == 1)
return min(nums1[i], nums2[j]); // 返回较小值
// 2/k 位置的值
// 如果一个数组 k/2 处超出范围, 无法判断中位数是否位于这个数组
// 但是另一个数组前 k/2 个肯定没有中位数
// 取 MAX, 淘汰另一个数组前 k/2 个元素
int mid1 = (i + k/2 - 1 < nums1.size()) ? nums1[i + k/2 - 1] : INT_MAX;
int mid2 = (j + k/2 - 1 < nums2.size()) ? nums2[j + k/2 - 1] : INT_MAX;
// 递归二分
if (mid1 < mid2) // mid1 淘汰 k/2
return findKth(nums1, i + k/2, nums2, j, k - k/2);
else // mid2 淘汰 k/2
return findKth(nums1, i, nums2, j + k/2, k - k/2);
}
};
