关于二分，之前也写过一篇，参考二分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;//就这一句不同,yydsint 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。
• 如果 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，继续二分查找。

具体实现代码（详解版）：

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] 太大，缩小 iright = i - 1;} else {// nums2[j-1] 太大，增大 ileft = i + 1;}}return 0.0;}
};

• 时间复杂度：O(log(min(m,n))
• 空间复杂度：O(1)