二分查找

二分查找介绍

核心思想

• 一种在有序数组中高效定位目标元素的方法,每次将查找区间缩小一半，从而快速锁定目标位置
• 经典的减而治之思想,所谓减，就是每一步都通过条件判断，排除掉一部分一定不包含目标元素的区间，从而缩小问题规模；治，则是在缩小后的区间内继续解决剩下的子问题。也就是说，二分查找的核心在于：每次查找都排除掉不可能存在目标的区间，仅在可能存在目标的区间内继续查找

模板

我喜欢的是左闭右闭的区间:

1. 区间定义：使用左闭右闭区间 [left, right]
2. 中间计算：mid = (left + right)/2 或 mid = left + (right - left)/2（防溢出）
3. 边界更新：

• 目标在右半区间：left = mid + 1
• 目标在左半区间：right = mid - 1

4. 终止条件：left > right 时查找失败

---

hot100中二分查找题目实践

1. 搜索插入位置

LeetCode 35. 搜索插入位置

问题描述： 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。请必须使用时间复杂度为 O(log n) 的算法。

二分思路 左闭右闭区间，使用left和right，计算mid，每次比较中间值与target，再决定是左区间还是右区间

代码实现

int searchInsert(int* nums, int numsSize, int target){
    int left=0,right=numsSize-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(nums[mid]>target){
            right=mid-1;
        }
        else if(nums[mid]<target){
            left=mid+1;
        }
        else{
            return mid;
        }
    }
    // 举例子发现，如果没找到mid，则就是在left指针
    return left;
}

本题中的return left：

在二分查找过程中，left 始终维护的是 target 应该插入的最小合法位置,更准确地说：left 是第一个满足 nums[i] >= target 的下标 i。这正是“插入位置”的定义：把 target 插入后，数组仍然有序。

---

2. 搜索二维矩阵

LeetCode 74. 搜索二维矩阵

问题描述： 给出m x n 整数矩阵：每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false

二分思路 若将矩阵每一行拼接在上一行的末尾，则会得到一个升序数组，我们可以在该数组上二分找到目标元素,代码实现时，可以二分升序数组的下标，将其映射到原矩阵的行和列上

代码实现

bool searchMatrix(int** matrix, int matrixSize, int* matrixColSize, int target) {
    int m = matrixSize, n = matrixColSize[0];
    int low = 0, high = m * n - 1;
    while (low <= high) {
        int mid = (high - low) / 2 + low;
        int x = matrix[mid / n][mid % n];
        if (x < target) {
            low = mid + 1;
        } else if (x > target) {
            high = mid - 1;
        } else {
            return true;
        }
    }
    return false;
}

• 时间复杂度：O(log mn)，其中 m 和 n 分别是矩阵的行数和列数
• 空间复杂度：O(1)

---

3. 在排序数组中查找元素的第一个和最后一个位置

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

问题描述： 给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]。你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题

二分思路 使用下界lowerBound二分查找函数，找到第一个大于等于 target 的元素的下标（即插入位置），也就是 target 的“左边界”，之后再根据target+1来找到右边界

代码实现

int lowerBound(int* nums,int numsSize,int target){
    int left=0,right=numsSize-1;
    while(left<=right){
        int mid=left+(right-left)/2;
        if(nums[mid]>=target){
            right=mid-1;
        } else{
            left=mid+1;
        }
    }
    return left;
}

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int* ret=(int*)malloc(sizeof(int)*2);
    *returnSize=2;

    int start=lowerBound(nums,numsSize,target);
    if(start==numsSize || nums[start]!=target){
        ret[0]=-1;
        ret[1]=-1;
        return ret;
    }
    // 返回的是：第一个 ≥ target + 1 的位置，所以这里要end再减一
    int end=lowerBound(nums,numsSize,target+1)-1;

    ret[0]=start;
    ret[1]=end;
    return ret;
}

本题思路巧妙在于：

使用lowerBound函数，找到第一个大于等于target的元素下标，之后再根据target+1找到右边界+1的位置，之后再减一就可以得到右边界，这一步很巧妙

---

4. 搜索旋转排序数组

LeetCode 33. 搜索旋转排序数组

问题描述： 整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k上进行了向左旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。

给你旋转后的数组 nums 和一个整数 target，如果 nums 中存在这个目标值 target，则返回它的下标，否则返回 -1。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二分思路 原数组升序且无重复，经一次旋转后，**任意中点 mid 必使左半段 [left, mid] 或右半段 [mid, right] 之一保持有序，接下来，利用nums[left]与nums[mid]比较，判断哪边有序，之后的思路如下：

• 左半段有序（nums[left] <= nums[mid]）：
  • 若 target ∈ [nums[left], nums[mid]) → 搜索左半：right = mid - 1
  • 否则 → 搜索右半：left = mid + 1
• 右半段有序（nums[left] > nums[mid]）：
  • 若 target ∈ (nums[mid], nums[right]] → 搜索右半：left = mid + 1
  • 否则 → 搜索左半：right = mid - 1

代码实现

int search(int* nums, int numsSize, int target){
    int left=0,right=numsSize-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 && nums[mid]>target){
                right=mid-1;
            } else{
                left=mid+1;
            }
        } else{
            if(nums[mid]<target && nums[right]>=target){
                left=mid+1;
            } else{
                right=mid-1;
            }
        }
    }
    return -1;
}

核心思路是：
原数组升序且无重复，经一次旋转后，**任意中点 mid 必使左半段 [left, mid] 或右半段 [mid, right] 之一保持有序

---

5. 寻找旋转排序数组中的最小值

LeetCode 153. 寻找旋转排序数组中的最小值

问题描述： 已知一个长度为n的数组，预先按照升序排列，经由1到n次旋转后，得到输入数组。注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]]

给你一个元素值互不相同的数组 nums ，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的最小元素 。

你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。

二分思路 最小值一定位于无序的那一半；如果某一半有序，则最小值不在其中，一直筛选出无序的数组区间，这里循环条件注意是while(left<right)，这样循环结束，left与right才能指向同一个值

代码实现

int findMin(int* nums, int numsSize) {
    int left = 0, right = numsSize - 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return nums[left];
}

---

6. 寻找两个正序数组的中位数

LeetCode 4. 寻找两个正序数组的中位数

问题描述： 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数,算法的时间复杂度应该为 O(log (m+n))

二分思路

在两个正序数组中找中位数的核心思想是：不合并数组，而是通过二分查找在较短数组上寻找一个“分割点”，使得左右两部分满足中位数的划分条件。
将 nums1 在位置 i 切分、nums2 在位置 j 切分，形成左右两部分。要求：

• 左半部分总元素数等于右半部分（或比右多 1），即 i + j = (m + n + 1) / 2；
• 左半部分的最大值不超过右半部分的最小值，即 nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]。
  为优化效率，始终在较短的数组上进行二分搜索。设 left = 0，right = m（i 的合法范围是 [0, m]）。每次取 i = left + (right - left) / 2，并令 j = k - i（其中 k = (m + n + 1) / 2）。
  为避免边界越界，使用 INT_MIN 和 INT_MAX 处理空侧：
• l1 = (i == 0) ? INT_MIN : nums1[i - 1]
• r1 = (i == m) ? INT_MAX : nums1[i]
• l2 = (j == 0) ? INT_MIN : nums2[j - 1]
• r2 = (j == n) ? INT_MAX : nums2[j]
  若 l1 <= r2 && l2 <= r1，说明分割正确：
• 若总长度为奇数，中位数为 max(l1, l2)；
• 若为偶数，中位数为 (max(l1, l2) + min(r1, r2)) / 2.0。
  否则：
• 若 l1 > r2，说明 i 太大，需左移：right = i - 1；
• 若 l2 > r1，说明 i 太小，需右移：left = i + 1。

代码实现

// 寻找中位数的函数
double findMedianSortedArrays(int* nums1, int m, int* nums2, int n) {
    // 确保 nums1 是较短的数组
    if (m > n) {
        // 交换 nums1 和 nums2，确保 nums1 总是较小的数组
        int* temp = nums1;
        nums1 = nums2;
        nums2 = temp;
        int tmp = m;
        m = n;
        n = tmp;
    }

    // 如果 nums1 或 nums2 为空数组，直接返回结果
    if (m == 0) {
        if ((m + n) % 2 == 1) {
            return nums2[(n - 1) / 2]; // 中位数
        } else {
            return (nums2[(n / 2) - 1] + nums2[n / 2]) / 2.0;
        }
    }

    // 设置 k 为合并后的中位数所在的位置
    int k = (m + n + 1) / 2;  // 求中位数位置

    int left = 0, right = m;
    while (left <= right) {
        int i = left + (right - left) / 2;  // nums1 的分割点
        int j = k - i;                      // nums2 的分割点

        // 获取 nums1 和 nums2 的边界元素
        int l1 = (i == 0) ? INT_MIN : nums1[i - 1]; // nums1 左边的最大值
        int r1 = (i == m) ? INT_MAX : nums1[i];     // nums1 右边的最小值
        int l2 = (j == 0) ? INT_MIN : nums2[j - 1]; // nums2 左边的最大值
        int r2 = (j == n) ? INT_MAX : nums2[j];     // nums2 右边的最小值

        if (l1 <= r2 && l2 <= r1) {
            // 如果分割点正确，找到中位数
            int lmax = (l1 > l2) ? l1 : l2;
            int rmin = (r1 < r2) ? r1 : r2;

            // 如果总数是奇数，返回左半部分的最大值
            if ((m + n) % 2 == 1) {
                return lmax;
            } else {
                // 如果总数是偶数，返回左右两边的平均值
                return (lmax + rmin) / 2.0;
            }
        } else if (l1 > r2) {
            // 如果 l1 > r2，则减少 nums1 的分割点，增加 nums2 的分割点
            right = i - 1;
        } else {
            // 如果 l2 > r1，则增加 nums1 的分割点，减少 nums2 的分割点
            left = i + 1;
        }
    }

    return -1;  // 如果没有找到合适的分割点，返回 -1
}

---

总结

本文围绕 LeetCode Hot100 中六道典型题目，系统梳理了二分查找在一维与二维场景下的多种变体应用：

1. 基础形式（如搜索插入位置）：直接在单调数组中查找目标或确定插入点，使用标准左闭右闭模板即可
2. 二维扩展（如搜索二维矩阵）：将二维结构逻辑上展平为一维升序序列，通过下标映射实现二分
3. 边界查找（如查找元素首尾位置）：借助下界（lower bound）思想，两次调用二分分别定位左右边界
4. 旋转数组处理（如搜索旋转排序数组、寻找最小值）：利用旋转后“至少一半有序”的性质，通过判断哪一侧有序来决定搜索方向；找最小值时则聚焦于“无序侧必含最小值”的特性
5. 跨数组二分（如寻找两个正序数组的中位数）：不合并数组，而是在较短数组上二分“分割点”，使得左右两部分满足中位数划分条件，体现了二分思想在更复杂结构中的灵活运用

核心思想： 明确搜索空间、设计合理的判断条件以排除无效区间、正确更新边界并处理边界情况