算法面试突击手册 —— 二分查找

一、概念与特点

大白话 + 类比

二分查找 = 猜数字游戏

甲心里想一个 1～100 的数，乙来猜。乙每次猜完，甲只会说”大了”或”小了”。聪明策略是每次猜中间的数：第一次猜 50，如果大了就猜 25，如果小了就猜 75……每次排除一半的可能性，100 个数只需最多 7 次就能猜中。这就是二分：每次把搜索空间砍半，O(log n)。

二分不只有序数组能用。凡是满足”单调性”或”二段性”的场景都能二分：某条分界线左边全满足、右边全不满足，二分就是找这条分界线。

核心特征（什么时候该想到用它）

特征说明
有序数组最直接的信号，标准二分
”找第一个/最后一个”搜索左右边界
旋转排序数组部分有序，仍可二分
答案有单调性值越大越满足条件（如最小化最大值）
数据量极大O(log n) 是唯一的可行复杂度

识别信号词

  • “有序数组”、“排序” → 直接二分
  • “旋转”、“部分有序” → 变种二分
  • “O(log n)” 时间要求 → 几乎必然是二分
  • “第一个”、“最后一个”、“等于 target” → 边界二分
  • “峰值”、“最小值” → 二分找拐点

二、应用场景

万能二分模板

// 模板一：查找 target（标准二分）
int left = 0, right = nums.length - 1;
while (left <= right) {
    int mid = left + (right - left) / 2; // 防溢出
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;

// 模板二：查找左边界（第一个 >= target）
int left = 0, right = nums.length;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) right = mid;   // 收缩右边界
    else left = mid + 1;
}
return left; // left == right

// 模板三：查找右边界（最后一个 <= target）
int left = 0, right = nums.length;
while (left < right) {
    int mid = left + (right - left + 1) / 2; // 注意上取整
    if (nums[mid] <= target) left = mid;
    else right = mid - 1;
}
return left;

关键细节

  • mid = left + (right - left) / 2 防溢出，不用 (left+right)/2
  • 搜索区间到底是 [left, right] 还是 [left, right)，想清楚再写
  • 循环条件是 left <= right 还是 left < right，取决于区间定义

三、Hot 100 精讲题目

35. Search Insert Position 搜索插入位置

📌 给定排序数组和目标值，找到目标值的下标。如果不存在，返回它应该插入的位置。如 [1,3,5,6], target=5 → 2

🔍 解题分析

核心思路：标准二分，找不到时 left 就是插入位置。等价于找第一个 >= target 的位置。

✅ 完整 Java 实现

public int searchInsert(int[] nums, int target) {
    int left = 0, right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    // 循环结束时 left > right，left 就是应该插入的位置
    return left;
}

⏱ 复杂度分析

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

💡 记忆口诀

“标准二分找到返回，找不到 left 就是该在的地方”

74. Search a 2D Matrix 搜索二维矩阵

📌 矩阵每行有序递增，且下一行第一个元素 > 上一行最后一个元素。如 matrix=[[1,3,5,7],[10,11,16,20],[23,30,34,60]], target=3 → true

🔍 解题分析

核心技巧：把二维坐标映射为一维下标。矩阵 m×n，第 i 行 j 列 → index = i*n + j。反过来 i = index / n, j = index % n。然后就变成标准二分。

✅ 完整 Java 实现

public boolean searchMatrix(int[][] matrix, int target) {
    int m = matrix.length, n = matrix[0].length;
    int left = 0, right = m * n - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 一维坐标 → 二维坐标
        int midVal = matrix[mid / n][mid % n];

        if (midVal == target) return true;
        else if (midVal < target) left = mid + 1;
        else right = mid - 1;
    }

    return false;
}

⏱ 复杂度分析

  • 时间复杂度：O(log(mn))
  • 空间复杂度：O(1)

💡 记忆口诀

“二维当一维，坐标转换一下就行”

34. Find First and Last Position 在排序数组中查找元素的第一个和最后一个位置

📌 在排序数组中找 target 的起始和结束位置。如 [5,7,7,8,8,10], target=8 → [3,4]

🔍 解题分析

核心思路：分别查找左边界和右边界。

  • 左边界：找第一个 >= target 的位置
  • 右边界：找第一个 >= target+1 的位置 - 1（或者等价写一个找 <= target 的右边界）

推荐写法：写一个 findFirst(nums, target) 找 >= target 的首位，然后 findFirst(nums, target+1) - 1 就是右边界。复用同一个函数，不易出错。

✅ 完整 Java 实现

public int[] searchRange(int[] nums, int target) {
    int left = findFirst(nums, target);
    if (left == nums.length || nums[left] != target) {
        return new int[]{-1, -1}; // target 不存在
    }
    // 右边界 = 第一个 >= target+1 的位置 - 1
    int right = findFirst(nums, target + 1) - 1;
    return new int[]{left, right};
}

// 万能函数：找第一个 >= target 的下标
private int findFirst(int[] nums, int target) {
    int left = 0, right = nums.length; // 注意：right = nums.length

    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid;  // 收缩右边界，保留 mid
        } else {
            left = mid + 1;
        }
    }

    return left; // left == right
}

⏱ 复杂度分析

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

💡 记忆口诀

“左边界找第一个 >= target，右边界用 target+1 减一偷懒”

33. Search in Rotated Sorted Array 搜索旋转排序数组

📌 排序数组在某点旋转（如 [0,1,2,4,5,6,7] 在 3 处旋转 → [4,5,6,7,0,1,2]），查找 target。要求 O(log n)。

🔍 解题分析

核心思路：虽然整体无序，但二分后至少有一半是有序的。判断 target 是否在有序的那半，是就进去，不是就去另一半。

步骤：

  1. 计算 mid，判断 nums[left] <= nums[mid]（左半是否有序）还是 nums[mid] <= nums[right]（右半有序）
  2. 判断 target 是否在有序的那半区间内
  3. 是 → 搜索那半；否 → 搜索另一半

易错点：nums[left] <= nums[mid] 这里的 = 很重要，处理 [3,1] 这种两个元素的情况。

✅ 完整 Java 实现

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 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; // target 在左半
            } else {
                left = mid + 1;  // target 在右半
            }
        } else {
            // 右半有序
            if (nums[mid] < target && target <= nums[right]) {
                left = mid + 1;  // target 在右半
            } else {
                right = mid - 1; // target 在左半
            }
        }
    }

    return -1;
}

⏱ 复杂度分析

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

💡 记忆口诀

“二分后总有一半有序，判断 target 在不在这半就行”

153. Find Minimum in Rotated Sorted Array 寻找旋转排序数组中的最小值

📌 不含重复元素的旋转排序数组，找最小值。如 [3,4,5,1,2] → 1

🔍 解题分析

核心思路：最小值就是旋转点。二分判断：若 nums[mid] > nums[right]，说明最小值在 mid 右边；否则在 mid 及其左边。

类比：你把一根递增的纸条在某处折了一下。最小值在折断处。二分时看中间点：如果中间点比最右边大，说明中间点还在上升段，折断处一定在右边；否则折断处在左边。

✅ 完整 Java 实现

public int findMin(int[] nums) {
    int left = 0, right = nums.length - 1;

    while (left < right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] > nums[right]) {
            // mid 比 right 大，最小值在 mid 右边（不含 mid）
            left = mid + 1;
        } else {
            // mid <= right，最小值可能是 mid 或在 mid 左边
            right = mid;
        }
    }

    return nums[left]; // left == right
}

⏱ 复杂度分析

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

💡 记忆口诀

“比 right 大就去右边，否则留在左边找”

4. Median of Two Sorted Arrays 寻找两个正序数组的中位数

📌 给定两个有序数组 nums1 和 nums2，找它们合并后的中位数。要求 O(log(m+n))。如 [1,3] 和 [2] → 2.0

🔍 解题分析

核心思路（转换问题）：中位数 = 把两个数组分成”左半”和”右半”，满足左半长度 = 右半长度（或差 1），且左半最大值 ≤ 右半最小值。

关键操作：在较短的数组上二分，确定它在左半的贡献量 i，则另一个数组在左半的贡献量 j 自然确定（j = (m+n+1)/2 - i）。判断划分是否合法：nums1[i-1] <= nums2[j] 且 nums2[j-1] <= nums1[i]。

✅ 完整 Java 实现

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    // 在较短的数组上二分，保证 O(log(min(m,n)))
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.length, n = nums2.length;
    int totalLeft = (m + n + 1) / 2; // 左半部分元素个数

    int left = 0, right = m; // nums1 的二分范围

    while (left <= right) {
        int i = left + (right - left) / 2; // nums1 在左半的贡献
        int j = totalLeft - i;              // nums2 在左半的贡献

        // 边界值：越界时用极值
        int nums1LeftMax  = (i == 0) ? Integer.MIN_VALUE : nums1[i - 1];
        int nums1RightMin = (i == m) ? Integer.MAX_VALUE : nums1[i];
        int nums2LeftMax  = (j == 0) ? Integer.MIN_VALUE : nums2[j - 1];
        int nums2RightMin = (j == n) ? Integer.MAX_VALUE : nums2[j];

        if (nums1LeftMax <= nums2RightMin && nums2LeftMax <= nums1RightMin) {
            // 划分成功
            if ((m + n) % 2 == 0) {
                return (Math.max(nums1LeftMax, nums2LeftMax)
                      + Math.min(nums1RightMin, nums2RightMin)) / 2.0;
            } else {
                return Math.max(nums1LeftMax, nums2LeftMax);
            }
        } else if (nums1LeftMax > nums2RightMin) {
            // nums1 在左半的太多，减小 i
            right = i - 1;
        } else {
            // nums2LeftMax > nums1RightMin，增大 i
            left = i + 1;
        }
    }

    return 0.0; // 不会到这里
}

⏱ 复杂度分析

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

💡 记忆口诀

“短数组上二分分界线，保证左半最大值 ≤ 右半最小值”

🔜 上一章：05-栈与单调栈 | 下一章：07-排序