跳到主要内容

二分查找算法练习

二分查找（Binary Search）要求数据集有序（或具有局部的单调性）。核心是定义搜索空间并逐步收缩。考察难点在于边界处理和旋转数组等变体。

35. 搜索插入位置 (Search Insert Position)​

题目描述​

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

解题思路​

典型的二分查找找左边界。如果 nums[mid] < target 则左移，否则收缩右界。

Java 代码实现​

class Solution {
    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;
        }
        return left;
    }
}

74. 搜索二维矩阵 (Search a 2d Matrix)​

题目描述​

编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一行的最后一个整数。

解题思路​

将二维矩阵看作一个展平的一维数组。对于一维索引 idx，其在二维中的坐标为 r = idx / n, c = idx % n。

Java 代码实现​

class Solution {
    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 val = matrix[mid / n][mid % n];
            if (val == target) return true;
            else if (val < target) left = mid + 1;
            else right = mid - 1;
        }
        return false;
    }
}

34. 在排序数组中查找元素的第一个和最后一个位置 (Find First and Last Position of Element in Sorted Array)​

题目描述​

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

解题思路​

实现两个辅助函数分别查找第一个和最后一个位置。

  • 第一个位置：nums[mid] >= target 时收缩右边界。
  • 最后一个位置：nums[mid] <= target 时收缩左边界。

Java 代码实现​

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int l = find(nums, target, true);
        int r = find(nums, target, false);
        return new int[]{l, r};
    }
    private int find(int[] nums, int target, boolean first) {
        int res = -1, L = 0, R = nums.length - 1;
        while (L <= R) {
            int mid = L + (R - L) / 2;
            if (nums[mid] == target) {
                res = mid;
                if (first) R = mid - 1; else L = mid + 1;
            } else if (nums[mid] < target) L = mid + 1;
            else R = mid - 1;
        }
        return res;
    }
}

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

题目描述​

整数数组 nums 按升序排列，但可能在某个点进行了旋转。给你 旋转后 的数组 nums 和一个整数 target ，如果数组中存在这个目标值，则返回它的下标，否则返回 -1 。

解题思路​

二分查找。每次剖开数组，必然有一半是有序的。判断 target 是否处于有序的那一半中。

Java 代码实现​

class Solution {
    public int search(int[] nums, int target) {
        int l = 0, r = nums.length - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) return mid;
            if (nums[l] <= nums[mid]) { // 左侧有序
                if (target >= nums[l] && target < nums[mid]) r = mid - 1;
                else l = mid + 1;
            } else { // 右侧有序
                if (target > nums[mid] && target <= nums[r]) l = mid + 1;
                else r = mid - 1;
            }
        }
        return -1;
    }
}

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

题目描述​

已知一个长度为 n 的数组，预先按照升序排列，并经 1 到 n 次旋转。找出其中的最小元素。

解题思路​

比较 nums[mid] 和 nums[right]。

  • 如果 nums[mid] < nums[right]，说明右侧有序，最小值在左侧（包含 mid）。
  • 如果 nums[mid] > nums[right]，说明分界点在右侧，左侧有序且较大，移向 mid + 1。

Java 代码实现​

class Solution {
    public int findMin(int[] nums) {
        int l = 0, r = nums.length - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] < nums[r]) r = mid;
            else l = mid + 1;
        }
        return nums[l];
    }
}

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

题目描述​

给定两个大小分别为 m 和 n 的正序数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。要求时间复杂度为 O(log (m+n))。

解题思路​

查找第 k 小的数。每次比较两个数组中 k/2 的位置。将其中较小的那一部分排除。

Java 代码实现​

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int n = nums1.length + nums2.length;
        if (n % 2 == 1) return getKth(nums1, 0, nums2, 0, n / 2 + 1);
        else return (getKth(nums1, 0, nums2, 0, n / 2) + getKth(nums1, 0, nums2, 0, n / 2 + 1)) / 2.0;
    }
    private int getKth(int[] n1, int i1, int[] n2, int i2, int k) {
        if (i1 >= n1.length) return n2[i2 + k - 1];
        if (i2 >= n2.length) return n1[i1 + k - 1];
        if (k == 1) return Math.min(n1[i1], n2[i2]);
        int mid1 = (i1 + k / 2 - 1 < n1.length) ? n1[i1 + k / 2 - 1] : Integer.MAX_VALUE;
        int mid2 = (i2 + k / 2 - 1 < n2.length) ? n2[i2 + k / 2 - 1] : Integer.MAX_VALUE;
        if (mid1 < mid2) return getKth(n1, i1 + k / 2, n2, i2, k - k / 2);
        else return getKth(n1, i1, n2, i2 + k / 2, k - k / 2);
    }
}