面试经典 150 题-二分查找

LeetCode 面试经典 150 题-二分查找

搜索插入位置

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

搜索二维矩阵

z字形查找

从右上角开始搜索，如果当前位置元素小于target，那么i+1，否则j-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }
}
  • 时间复杂度：O(m + n)
  • 空间复杂度：O(1)

二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;
        int left = 0, right = m * n - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            int x = matrix[mid / n][mid % n];
            if (x == target) {
                return true;
            } else if (x < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return false;
    }
}
  • 时间复杂度：O(logmn)
  • 空间复杂度：O(1)

寻找峰值

二分查找

通过每次将搜索区间减半，优化查找过程。我们不需要检查每个元素，只需检查中间元素与其相邻元素的关系，从而缩小范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findPeakElement(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] < nums[mid + 1]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

搜索旋转排序数组

二分查找

判断哪一部分是有序的，并根据有序的那个部分确定我们该如何改变二分查找的上下界：

  • 如果 [left, mid - 1] 是有序数组，即nums[left] <= nums[mid]：如果target >= nums[left] && target < nums[mid]，则在左半部分，否则在右半部分；
  • 否则如果nums[left] > nums[mid]，则右半部分有序：如果target > nums[mid] && target <= nums[right]，则在右半部分，否则在左半部分。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            }
            // 左半部分有序
            if (nums[mid] >= nums[left]) {
                // 在左边
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    // 在右边
                    left = mid + 1;
                }
            } else {
                // 右半部分有序
                // 在右边
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    // 在左边
                    right = mid - 1;
                }
            }
        }

        return -1;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

搜索旋转排序数组II

二分查找

  1. 判断 nums[mid] 是否等于 target，如果是，直接返回 true。
  2. 如果左边有序（即 nums[left] <= nums[mid]），那么我们可以通过比较 target 和 nums[left]、nums[mid] 来判断 target 是否在这个有序区间内，从而决定向左还是向右查找。
  3. 如果右边有序（即 nums[mid] <= nums[right]），则可以类似地判断 target 是否在这个有序区间内，并决定查找方向。
  4. 如果左右两边有重复元素（即 `nums[left] == nums[mid] || nums[mid] == nums[right]），我们只能通过将左右边界向内缩小来减少搜索范围。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {
    public boolean 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 true;
            }
            
            // 左侧有序
            if (nums[left] < nums[mid]) {
                // target 是否在左侧有序部分
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
            // 右侧有序
            else if (nums[mid] < nums[right]) {
                // target 是否在右侧有序部分
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            // 无法确定有序部分，逐步缩小区间
            else {
                // 去除重复元素
                if (nums[left] == nums[mid]) {
                    left++;
                }
                if (nums[right] == nums[mid]) {
                    right--;
                }
            }
        }
        
        return false;
    }
}
  • 时间复杂度：O(n)，最坏情况下，由于重复元素的存在。
  • 空间复杂度：O(1)

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

二分查找

要找到数组中第一个等于目标元素的位置和第一个大于目标元素的位置-1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        }
        return new int[]{-1, -1};
    }

    // 二分查找，lower为true查找第一个大于等于target的下标，否则查找第一个大于target的下标
    public int binarySearch(int[] nums, int target, boolean lower) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = (left + right) >> 1;
            // 向左收缩边界
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;  // mid是可能的答案
            } else {
                // 向右收缩边界
                left = mid + 1;
            }
        }
        return ans;
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

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

二分查找

如果nums[mid] > nums[right]，则最小值一定在mid右侧；否则一定是mid或mid的左侧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            // 在左侧
            if (nums[mid] < nums[right]) {
                right = mid;
            } else {
                // 在右侧
                left = mid + 1;
            }
        }
        return nums[left];
    }
}
  • 时间复杂度：O(logn)
  • 空间复杂度：O(1)

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

二分查找

  1. 确保 nums1 是较小的数组：我们总是对较短的数组进行二分查找，减少搜索空间。
  2. 二分查找：在较短数组中查找一个合适的分割点，使得两数组的左半部分和右半部分满足合并后的中位数条件。
  3. 计算中位数：
    • 如果数组的总长度为奇数，中位数是左半部分的最大值。
    • 如果数组的总长度为偶数，中位数是左半部分最大值与右半部分最小值的平均值。

Alt text

Alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 保证nums1是长度较短的那个
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) {
            return findMedianSortedArrays(nums2, nums1);
        }
        // 初始化
        int k = (m + n + 1) / 2;
        int left = 0, right = m;
        while (left <= right) {
            // 划分数组
            int i = (left + right) >> 1;
            int j = k - i;
            // 交叉比较
            // 左下大于右上，i需要增大
            if (j != 0 && i != m && nums2[j-1] > nums1[i]) {
                left = i + 1;
            } else if (i != 0 && j != n && nums1[i-1] > nums2[j]) {
                // 左上大于右下，i需要减小
                right = i - 1;
            } else {
                // 满足要求，先求左边最大值
                int maxLeft = 0;
                // 数组一没有元素存在于左半部分
                if (i == 0) {
                    maxLeft = nums2[j - 1];
                } else if (j == 0) {
                    // 数组二没有元素存在于左半部分
                    maxLeft = nums1[i - 1];
                } else {
                    // 两者取较大
                    maxLeft = Math.max(nums1[i-1], nums2[j-1]);
                }

                // 奇数不需要考虑右半部分
                if ((m + n) % 2 == 1) {
                    return maxLeft;
                }

                // 如果是偶数，需要考虑右边
                int minRight = 0;
                // 数组1没有元素存在于右半部分
                if (i == m) {
                    minRight = nums2[j];
                } else if (j == n) {
                    // 数组2没有元素存在于右半部分
                    minRight = nums1[i];
                } else {
                    // 两者取较小
                    minRight = Math.min(nums1[i], nums2[j]);
                }
                return (maxLeft + minRight) / 2.0;

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

总结

二分查找的题目总体来说不难，但是对于边界的判断容易混淆，以后要多加复习。

算法笔记 > 二分查找
#二分查找
面试经典 150 题-二分查找
http://example.com/2025/02/28/posts/hot150-14/
作者
Xuan Yang
发布于
2025年2月28日
许可协议