关于二分，之前也写过一篇，参考二分Acwing
1.搜索插入位置
思路分析：典型的 二分查找算法，用于在一个已排序的数组中查找目标值的位置。如果找到了目标值，返回其索引；如果没有找到，则返回目标值应该插入的位置。
- 初始化左右边界
- 二分查找
- 每次计算mid，通过 mid = left + (right - left) / 2 来避免可能的溢出；
- 如果目标值 target 与 nums[mid] 相等，则返回 mid
- 如果 nums[mid] 大于 target，则将右边界 right 移动到 mid - 1，继续在左半边查找；
- 如果 nums[mid] 小于 target，则将左边界 left 移动到 mid + 1，继续在右半边查找。
- 返回插入位置：如果没有找到目标值，left 会指向目标值应该插入的位置。此时，left 就是目标值应该插入的索引。
具体实现代码（详解版):
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1; // 初始化左右边界
while (left <= right) { // 当左边界不超过右边界时继续查找
int mid = left + (right - left) / 2; // 计算中间位置，避免溢出
if (nums[mid] == target) { // 如果找到了目标值
return mid; // 返回该值的索引
} else if (nums[mid] > target) { // 如果目标值小于中间值
right = mid - 1; // 向左半边查找
} else { // 如果目标值大于中间值
left = mid + 1; // 向右半边查找
}
}
return left; // 返回左边界位置，即目标值应插入的位置
}
};
- 时间复杂度：O（log n），每次查找都会将搜索空间减小一半，最多执行log n次；
- 空间复杂度：O（1）
2.搜索二维矩阵
思路分析：由于每一行是升序排列的，而且每列也是升序排列的，我们可以通过二分查找直接在二维矩阵中进行查找，而不需要将矩阵展平为一维数组。
- 单一的二分查找：我们将二维矩阵视为一个有序的 1D 数组，矩阵的元素总数是 m * n。关键点是将每个中间索引 mid 映射到二维矩阵中的位置，mid / n 对应行，mid % n 对应列。；
- 索引映射：通过 mid / n 得到对应的行索引，通过 mid % n 得到列索引。这种映射方式相当于将矩阵展平，但不需要额外的空间。
具体实现代码（详解版）：
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int m = matrix.size();
int n = matrix[0].size();
int left = 0, right = m * n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
//就这一句不同,yyds
int midValue = matrix[mid / n][mid % n]; // 将 1D 索引转换为 2D 索引
if (midValue == target) {
return true;
} else if (midValue < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return false;
}
};
- 时间复杂度：O（log（m * n))
- 空间复杂度：O（1）
3.在排序数组中查找元素的第一个和最后一个位置
思路分析：这个问题可以分为两个子问题：查找目标值的起始位置，查找目标值的结束位置；
-
1.查找起始位置
- 设定两个指针，分别指向数组的左右端点；
- 在每次比较时，我们计算中间位置 mid，然后根据数组的值来调整左右边界；
- 如果 nums[mid] 大于或等于 target，我们就缩小右边界 r = mid，因为目标值可能在当前的 mid 或左边部分。
- 如果 nums[mid] 小于 target，说明目标值在右边，因此移动左边界 l = mid + 1。
- 当 l 和 r 收敛时，我们检查 nums[l] 是否等于 target，如果是，l 就是目标值的 起始位置。
-
2.查找结束位置
- 查找 结束位置 的方法与查找起始位置非常相似，但这次我们需要找到 最后一个出现的目标值。因此，在二分查找过程中，当目标值出现时，我们继续往右查找，直到找到最后一个目标值。
- 使用两个指针 l2 和 r2，开始时设定为整个数组的范围。
- 计算中间位置 mid，并根据 nums[mid] 和 target 的关系来调整左右边界：
- 如果 nums[mid] 小于或等于 target，我们可能找到了目标值的最后位置，因此继续向右查找，调整 l2 = mid。
- 如果 nums[mid] 大于 target，则目标值只能在 mid 左边，因此调整右边界 r2 = mid - 1。
- 当 l2 和 r2 收敛时，l2 就是目标值的 结束位置。
具体实现代码（详解版)
class Solution {
public:
vector<int> searchRange(vector<int>& nums, int target) {
vector<int> res = {-1, -1};
if (nums.empty()) {
return res;
}
// 查找目标值的起始位置
int l = 0, r = nums.size() - 1;
while (l < r) {
int mid = l + (r - l) / 2; // 防止溢出
if (nums[mid] >= target) {
r = mid; // 目标值可能在左半部分或是 mid 本身
} else {
l = mid + 1;
}
}
// 确保 nums[l] 是目标值
if (nums[l] != target) {
return res; // 如果没有找到目标值，直接返回 {-1, -1}
}
int start = l;
// 查找目标值的结束位置
int l2 = 0, r2 = nums.size() - 1;
while (l2 < r2) {
int mid = l2 + (r2 - l2 + 1) / 2; // 防止溢出
if (nums[mid] <= target) {
l2 = mid; // 目标值可能在右半部分或是 mid 本身
} else {
r2 = mid - 1;
}
}
int end = l2;
// 返回目标值的起始位置和结束位置
return {start, end};
}
};
- 时间复杂度：O（log n）；
- 空间复杂度：O(1)
4.搜搜旋转排序数组
思路分析：旋转后的数组会分为两个升序的部分：一部分可能是从旋转点到数组的末尾，另一部分是从数组的开头到旋转点。我们可以利用二分查找，但需要判断中间元素的位置是处于旋转后的哪个部分。通过这个判断，我们能够缩小搜索范围。
- 初始化两个指针 left 和 right，分别指向数组的头和尾。；
- 计算中间位置 mid = left + (right - left) / 2
- 判断 nums[mid] 是否等于目标值 target，如果是，直接返回 mid。
- 判断 nums[mid] 是否等于目标值 target，如果是，直接返回 mid。
- 如果左半部分升序：nums[left] <= nums[mid]，此时：
- 如果 nums[left] <= target < nums[mid]，目标值在左半部分，更新 right = mid - 1；
- 否则，目标值在右半部分，更新 left = mid + 1。
- 如果右半部分升序：nums[mid] <= nums[right]，此时：
- 如果 nums[mid] < target <= nums[right]，目标值在右半部分，更新 left = mid + 1；
- 否则，目标值在左半部分，更新 right = mid - 1。
- 如果左半部分升序：nums[left] <= nums[mid]，此时：
- 如果 left 超过 right，说明目标值不存在于数组中，返回 -1。
具体实现代码（详解版）：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (nums[mid] == target) {
return mid; // 找到目标值，返回索引
}
// 判断左半部分是否有序
if (nums[left] <= nums[mid]) {
// 如果目标值在左半部分
if (nums[left] <= target && target < nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else {
// 右半部分有序
// 如果目标值在右半部分
if (nums[mid] < target && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return -1; // 找不到目标值
}
};
5.寻找寻转数组中的最小值
思路分析：旋转的关键在于数组的最小值。最小值一定在旋转点处，旋转后的数组就像是两个升序数组拼接在一起，最小值一定是较小的部分的第一个元素。通过二分查找来高效地找到最小值的位置：
- 如果 nums[mid] >= nums[right]，说明旋转点在右半部分或是 mid 本身可能是旋转点的前一个位置。此时最小值必然在右半部分，我们将 left = mid + 1。
- 否则，说明最小值在左半部分或 mid 本身就是最小值，我们将 right = mid。
- 最终，left == right，nums[left]就是最小值。
具体实现代码（详解版）：
class Solution {
public:
int findMin(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
// 二分查找
while (left < right) {
int mid = left + (right - left) / 2;
// 如果 mid 元素大于右边的元素，最小值一定在右边
if (nums[mid] > nums[right]) {
left = mid + 1;
} else {
// 如果 mid 元素小于等于右边的元素，最小值可能在左边
right = mid;
}
}
// 当 left == right 时，left 就是最小值的位置
return nums[left];
}
};
6.寻找两个正序数组中的中位数
真实难题！
思路分析：由于我们需要在两个有序数组中找到中位数，可以考虑通过二分查找的方式，在一个数组中找到合适的分割点，并利用这个分割点将另一个数组分成合适的部分。
- 中位数的定义：如果合并两个数组后的总元素数是奇数，那么中位数就是中间那个元素；如果合并两个数组后的总元素数是偶数，那么中位数是中间两个元素的平均值。
- 通过二分查找进行分割
- 我们将数组 nums1 和 nums2 分成两部分，使得：
- 左边部分包含的是小于等于右边部分的元素。
- 两个数组的左部分和右部分的元素个数总是相等（或者左部分多一个）。
- 我们希望通过二分查找来找到数组 nums1 中的分割点 i，从而通过 i 可以推算出数组 nums2 中的分割点 j。
- 条件检查：对于每一对 i 和 j，我们检查是否满足：
- nums1[i-1] <= nums2[j]（nums1 左半部分最大值小于等于 nums2 右半部分最小值）
- nums2[j-1] <= nums1[i]（nums2 左半部分最大值小于等于 nums1 右半部分最小值）
- 如果满足条件，计算并返回中位数。
- 如果不满足上述条件，调整 i，继续二分查找。
- 我们将数组 nums1 和 nums2 分成两部分，使得：
具体实现代码（详解版）：
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
// 确保 nums1 是较小的数组
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size();
int n = nums2.size();
int left = 0, right = m;
while (left <= right) {
int i = left + (right - left) / 2; // nums1 的分割点
int j = (m + n + 1) / 2 - i; // nums2 的分割点
// 处理 nums1[i-1] 和 nums2[j-1] 可能越界的情况
int nums1LeftMax = (i == 0) ? INT_MIN : nums1[i - 1];
int nums1RightMin = (i == m) ? INT_MAX : nums1[i];
int nums2LeftMax = (j == 0) ? INT_MIN : nums2[j - 1];
int nums2RightMin = (j == n) ? INT_MAX : nums2[j];
// 检查是否找到了合适的分割点
if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
// 如果总数为奇数，返回左半部分最大值
if ((m + n) % 2 == 1) {
return max(nums1LeftMax, nums2LeftMax);
}
// 如果总数为偶数，返回两者中间的平均值
return (max(nums1LeftMax, nums2LeftMax) + min(nums1RightMin, nums2RightMin)) / 2.0;
}
else if (nums1LeftMax > nums2RightMin) {
// nums1[i-1] 太大，缩小 i
right = i - 1;
} else {
// nums2[j-1] 太大，增大 i
left = i + 1;
}
}
return 0.0;
}
};
- 时间复杂度：O(log(min(m,n))
- 空间复杂度：O(1)
![洛谷每日一题——B2143 进制转换、P1003 [NOIP2011 提高组] 铺地毯](https://i-blog.csdnimg.cn/direct/243085022350443abdbe0004d7cbda77.png)
