关于二分，之前也写过一篇，参考二分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。
- 如果左半部分升序：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] 太大，缩小 iright = i - 1;} else {// nums2[j-1] 太大，增大 ileft = i + 1;}}return 0.0;}
};- 时间复杂度：O(log(min(m,n))
- 空间复杂度：O(1)
