🔍 二分查找算法及变种形式详解

📖 概述

二分查找（Binary Search）是计算机科学中最基础、最重要的算法之一。它通过每次将搜索范围缩小一半的方式，在有序数组中高效地查找目标元素，时间复杂度为 O(log n)。

🎯 核心思想

二分查找的核心思想是：分治。通过比较中间元素与目标值，每次都能将搜索范围缩小一半，直到找到目标值或确定不存在。

🔢 基础二分查找

标准模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class BinarySearch {
    /**
     * 基础二分查找 - 查找目标值的索引
     * @param nums 有序数组
     * @param target 目标值
     * @return 目标值的索引，不存在返回 -1
     */
    public int binarySearch(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 -1; // 未找到目标
    }
}

基础二分查找测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
@Test
public void testBasicBinarySearch() {
    BinarySearch bs = new BinarySearch();
    int[] nums = {1, 3, 5, 7, 9, 11, 13, 15};
    
    // 测试存在的元素
    assertEquals(0, bs.binarySearch(nums, 1));  // 最左元素
    assertEquals(7, bs.binarySearch(nums, 15)); // 最右元素
    assertEquals(3, bs.binarySearch(nums, 7));  // 中间元素
    
    // 测试不存在的元素
    assertEquals(-1, bs.binarySearch(nums, 0));   // 小于最小值
    assertEquals(-1, bs.binarySearch(nums, 16));  // 大于最大值
    assertEquals(-1, bs.binarySearch(nums, 6));   // 中间缺失值
}

🔄 二分查找的变种形式

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
/**
 * 查找第一个等于目标值的元素 - 原始版本
 */
public int findFirstEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            // 找到目标值，但需要确认是否是第一个
            if (mid == 0 || nums[mid - 1] != target) {
                return mid;
            } else {
                right = mid - 1; // 继续在左半部分查找
            }
        }
    }
    
    return -1;
}

优化实现一：简化逻辑版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 查找第一个等于目标值的元素 - 优化版本1
 * 简化逻辑，减少嵌套层级
 */
public int findFirstEqualOptimized(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] >= target) {
            right = mid - 1;  // 向左收缩，寻找第一个等于target的位置
        } else {
            left = mid + 1;   // 向右收缩
        }
    }
    
    // 检查left是否在有效范围内，且nums[left]是否等于target
    return (left < nums.length && nums[left] == target) ? left : -1;
}

2. 查找最后一个等于目标值的元素

原始实现（可优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 查找最后一个等于目标值的元素 - 原始版本
 */
public int findLastEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            // 找到目标值，但需要确认是否是最后一个
            if (mid == nums.length - 1 || nums[mid + 1] != target) {
                return mid;
            } else {
                left = mid + 1; // 继续在右半部分查找
            }
        }
    }
    return -1;
}

优化实现一：简化逻辑版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 查找最后一个等于目标值的元素 - 优化版本1
 * 简化逻辑，减少嵌套层级
 */
public int findLastEqualOptimized(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;  // 向右收缩，寻找最后一个等于target的位置
        } else {
            right = mid - 1; // 向左收缩
        }
    }
    
    // 检查right是否在有效范围内，且nums[right]是否等于target
    return (right >= 0 && nums[right] == target) ? right : -1;
}

3. 查找第一个大于等于目标值的元素

原始实现（可优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 查找第一个大于等于目标值的元素 - 原始版本
 */
public int findFirstGreaterOrEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            // nums[mid] >= target
            if (mid == 0 || nums[mid - 1] < target) {
                return mid;
            } else {
                right = mid - 1;
            }
        }
    }
    return -1;
}

优化实现一：简化逻辑版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 查找第一个大于等于目标值的元素 - 优化版本1
 * 简化逻辑，减少嵌套层级
 */
public int findFirstGreaterOrEqualOptimized(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1;  // 向左收缩，寻找第一个大于等于target的位置
        } else {
            left = mid + 1;   // 向右收缩
        }
    }
    
    // 检查left是否在有效范围内，且nums[left]是否大于等于target
    return (left < nums.length && nums[left] >= target) ? left : -1;
}

4. 查找最后一个小于等于目标值的元素

原始实现（可优化）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 查找最后一个小于等于目标值的元素 - 原始版本
 */
public int findLastLessOrEqual(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        
        if (nums[mid] > target) {
            right = mid - 1;
        } else {
            // nums[mid] <= target
            if (mid == nums.length - 1 || nums[mid + 1] > target) {
                return mid;
            } else {
                left = mid + 1;
            }
        }
    }
    
    return -1;
}

优化实现一：简化逻辑版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 查找最后一个小于等于目标值的元素 - 优化版本1
 * 简化逻辑，减少嵌套层级
 */
public int findLastLessOrEqualOptimized(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;  // 向右收缩，寻找最后一个小于等于target的位置
        } else {
            right = mid - 1; // 向左收缩
        }
    }
    
    // 检查right是否在有效范围内，且nums[right]是否小于等于target
    return (right >= 0 && nums[right] <= target) ? right : -1;
}

🎯 应用案例详解

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

LeetCode 34：给定一个按照升序排列的数组，找到目标值的开始和结束位置。

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
public class Solution {
    /**
     * 查找第一个大于等于目标值的元素位置
     * 使用循环不变量思想，简化逻辑
     */
    private int lowerBound(int[] nums, int target) {
        int left = 0, right = nums.length - 1; // 闭区间 [left, right]
        
        while (left <= right) { // 区间不为空
            // 循环不变量：
            // nums[left-1] < target
            // nums[right+1] >= target
            int mid = left + (right - left) / 2;
            
            if (nums[mid] >= target) {
                right = mid - 1; // 范围缩小到 [left, mid-1]
            } else {
                left = mid + 1; // 范围缩小到 [mid+1, right]
            }
        }
        
        // 循环结束后 left = right+1
        // 此时 nums[left-1] < target 而 nums[left] = nums[right+1] >= target
        // 所以 left 就是第一个 >= target 的元素下标
        return left;
    }
    
    public int[] searchRange(int[] nums, int target) {
        int start = lowerBound(nums, target);
        // 检查是否找到目标值
        if (start == nums.length || nums[start] != target) {
            return new int[]{-1, -1}; // nums 中没有 target
        }
        
        // 查找最后一个等于目标值的位置
        // 通过查找第一个大于target的元素位置，然后减1
        int end = lowerBound(nums, target + 1) - 1;
        return new int[]{start, end};
    }
}

案例2：搜索插入位置

LeetCode 35：给定一个排序数组和一个目标值，如果目标值存在于数组中，返回其索引；如果不存在，返回它应该被插入的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public 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;
            }
        }
        
        // 如果没找到，left 就是应该插入的位置
        return left;
    }
}

案例3：搜索旋转排序数组

LeetCode 33：在旋转过的有序数组中查找目标值。

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
public class Solution {
    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; // 目标在左半边
                } else {
                    left = mid + 1;  // 目标在右半边
                }
            } else {
                // 右半边有序
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;  // 目标在右半边
                } else {
                    right = mid - 1; // 目标在左半边
                }
            }
        }
        
        return -1;
    }
}

案例4：寻找旋转排序数组中的最小值

LeetCode 153：在旋转排序数组中找到最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    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]) {
                // 最小值在右半部分
                left = mid + 1;
            } else {
                // 最小值在左半部分或就是 mid
                right = mid;
            }
        }
        
        return nums[left];
    }
}

案例5：x 的平方根

LeetCode 69：实现 int sqrt(int x) 函数，返回 x 的平方根的整数部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int mySqrt(int x) {
        if (x == 0) return 0;
        
        int left = 1, right = x;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 防止溢出，使用除法而不是乘法
            if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
                return mid;
            } else if (mid > x / mid) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        
        return right;
    }
}

案例6：购物系统降级规则

实际应用场景：购物APP核心系统面临集群故障，需要设计降级规则来限制客户端调用量。

问题描述：

  • 有N个客户端，每个客户端有不同的调用量R = [R₁, R₂, …, Rₙ]
  • 核心系统最大调用量为cnt
  • 如果总调用量sum® ≤ cnt，返回-1（正常调用）
  • 如果总调用量sum® > cnt，需要设定阈值value
  • 超过value的客户端限制为value，求最大可能的value

解决方案：使用二分查找寻找最大阈值

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
public class ShoppingSystemDegradation {
    /**
     * 计算购物系统降级阈值
     * @param R 各客户端调用量数组
     * @param cnt 系统最大调用量
     * @return 最大阈值value，如果总调用量不超过cnt则返回-1
     */
    public int findDegradationThreshold(int[] R, int cnt) {
        // 计算总调用量
        long total = 0;
        for (int num : R) {
            total += num;
        }
        
        // 如果总调用量不超过限制，返回-1（正常调用）
        if (total <= cnt) {
            return -1;
        }
        
        // 使用二分查找寻找最大阈值value
        int left = 0, right = getMax(R);
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            // 计算使用mid作为阈值时的总调用量
            long sumWithThreshold = calculateSumWithThreshold(R, mid);
            
            if (sumWithThreshold <= cnt) {
                // 当前阈值可以接受，尝试更大的值
                left = mid + 1;
            } else {
                // 当前阈值太大，需要减小
                right = mid - 1;
            }
        }
        // right就是最大的满足条件的阈值
        return right;
    }
    
    /**
     * 计算使用给定阈值时的总调用量
     */
    private long calculateSumWithThreshold(int[] R, int threshold) {
        long sum = 0;
        for (int num : R) {
            sum += Math.min(num, threshold);
        }
        return sum;
    }
    
    /**
     * 获取数组中的最大值
     */
    private int getMax(int[] R) {
        int max = 0;
        for (int num : R) {
            max = Math.max(max, num);
        }
        return max;
    }
    
    public static void main(String[] args) {
        ShoppingSystemDegradation solution = new ShoppingSystemDegradation();
        
        // 测试用例1：需要降级
        int[] R1 = {5, 3, 8, 2, 7};
        int cnt1 = 15;
        System.out.println("测试用例1：" + solution.findDegradationThreshold(R1, cnt1)); // 输出: 3
        
        // 测试用例2：不需要降级
        int[] R2 = {2, 3, 1, 4};
        int cnt2 = 20;
        System.out.println("测试用例2：" + solution.findDegradationThreshold(R2, cnt2)); // 输出: -1
        
        // 测试用例3：边界情况
        int[] R3 = {10, 10, 10};
        int cnt3 = 25;
        System.out.println("测试用例3：" + solution.findDegradationThreshold(R3, cnt3)); // 输出: 8
    }
}

算法分析：

  • 时间复杂度：O(n log m)，其中n是客户端数量，m是最大调用量
  • 空间复杂度：O(1)
  • 核心思想：通过二分查找快速定位最大阈值，避免线性搜索

⚡ 性能分析

时间复杂度

  • 基础二分查找：O(log n)
  • 所有变种形式：O(log n)

空间复杂度

  • 迭代实现：O(1)
  • 递归实现：O(log n)（递归栈空间）

性能对比

算法 时间复杂度 空间复杂度 适用场景
线性搜索 O(n) O(1) 无序数组
二分查找 O(log n) O(1) 有序数组
哈希表查找 O(1) 平均 O(n) 快速查找

🛠️ 实战练习

练习题1：寻找峰值

描述：峰值元素是指其值严格大于左右相邻值的元素。给定一个数组，找到峰值元素并返回其索引。

要求：时间复杂度 O(log n)

1
// 你的代码实现

练习题2：搜索二维矩阵

描述：编写一个高效的算法来搜索 m × n 矩阵中的一个目标值。该矩阵具有以下特性：

  • 每行中的整数从左到右按升序排列
  • 每行的第一个整数大于前一行的最后一个整数

要求：时间复杂度 O(log(m × n))

1
// 你的代码实现

练习题3：寻找重复数

描述：给定一个包含 n + 1 个整数的数组，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的数字。假设只有一个重复的数字，找出这个重复的数字。

要求：

  • 不能修改原数组（假设数组是只读的）
  • 只能使用额外的 O(1) 的空间
  • 时间复杂度小于 O(n²)
1
// 你的代码实现

📚 相关LeetCode题目

基础题目

进阶题目

高难度题目

🎯 关键要点总结

核心原则

  1. 有序性：二分查找的前提是数组必须有序
  2. 边界条件：注意处理 left、right、mid 的边界情况
  3. 溢出处理：使用 left + (right - left) / 2 而不是 (left + right) / 2
  4. 终止条件：理解 while (left <= right) 和 while (left < right) 的区别

常见陷阱

  1. 死循环：注意更新 left 和 right 时的边界条件
  2. 数组越界：检查 mid 的相邻元素是否存在
  3. 精度问题：处理整数溢出和浮点数比较
  4. 特殊情况：空数组、单元素数组等边界情况

优化技巧

  1. 位运算优化：使用 mid = left + ((right - left) >> 1) 提高性能
  2. 早停策略：在某些情况下可以提前终止搜索
  3. 缓存中间结果：避免重复计算

📖 参考资料

最后更新：2025-01-15