算法思想 - 二分查找算法

1. 二分查找理论

二分查找（Binary Search）是一种高效的查找方法。通过每次将查找范围折半，它的时间复杂度为 O(log⁡n)。适用于以下条件的数据集：

1. 数据必须是 顺序存储结构（如数组）。
2. 数据必须是 按关键字有序排列（通常为升序或降序）。

原理： 将查找范围逐步缩小，根据目标值（target）与中间值（mid）的比较结果，决定搜索的方向：

• 如果 target == mid，查找成功，返回结果。
• 如果 target < mid，缩小范围至左半部分。
• 如果 target > mid，缩小范围至右半部分。

重复以上操作，直到找到目标值或搜索范围为空。

2. 二分查找的精髓

二分查找的核心思想可以归纳为三个关键点：

1. 目标值小于中间值时怎么办？
2. 目标值等于中间值时怎么办？
3. 目标值大于中间值时怎么办？

从本质上看，二分查找是一个逻辑清晰的填空题。明确这三个关键点后，二分查找即可在 O(log⁡n) 的时间复杂度内解决查找问题。

基于以上三种情况，二分查找不仅能查找目标值是否存在，还能解决更多复杂问题，比如：

• 查找目标值的边界（第一次出现、最后一次出现）。
• 查找满足条件的数值（如第一个大于目标值的数）。

3. 二分查找的应用

3.1 查找目标值（无重复数据）

问题描述：

在一个升序数组中查找目标值的位置。如果目标值不存在，返回 -1。

示例：

输入数组 [1, 2, 3, 4, 5, 6, 7, 8, 9]，目标值 6。 输出：索引 5。

代码：

public int binarySearch(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1; // 初始查找范围
    while (left <= right) { // 范围有效时继续查找
        int middle = left + (right - left) / 2; // 计算中间位置
        if (numbers[middle] == target) {
            return middle; // 找到目标值
        } else if (numbers[middle] > target) {
            right = middle - 1; // 缩小右边界
        } else {
            left = middle + 1; // 缩小左边界
        }
    }
    return -1; // 未找到目标值
}

---

3.2 查找小于目标值的最后一个数字的位置

问题描述：

在一个升序数组中查找最后一个小于目标值的数字的位置。

示例：

输入数组 [1, 2, 2, 3, 3, 3, 4, 5]，目标值 3。 输出：索引 3（最后一个小于 3 的数字是 2，位置为 3）。

代码：

public int findLastSmaller(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2; // 计算中间位置
        if (numbers[middle] < target) {
            left = middle + 1; // 更新左边界，尝试找到更靠右的小于目标值的数字
        } else {
            right = middle - 1; // 缩小右边界
        }
    }
    return right; // 最后一个小于目标值的位置
}

---

3.3 查找目标值第一次出现的位置

问题描述：

在一个升序数组中，查找目标值第一次出现的位置。

示例：

输入数组 [1, 1, 2, 2, 3, 3, 3, 4]，目标值 3。 输出：索引 4（3 第一次出现在索引 4 位置）。

代码：

public int findFirstOccurrence(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2; // 计算中间位置
        if (numbers[middle] >= target) { 
            right = middle - 1; // 缩小右边界，继续查找左边
        } else {
            left = middle + 1; // 缩小左边界
        }
    }
    return (left < numbers.length && numbers[left] == target) ? left : -1; // 检查是否找到
}

---

3.4 查找目标值最后一次出现的位置

问题描述：

在一个升序数组中，查找目标值最后一次出现的位置。

示例：

输入数组 [1, 1, 2, 2, 3, 3, 3, 4]，目标值 3。 输出：索引 6（3 最后一次出现在索引 6 位置）。

代码：

public int findLastOccurrence(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2; // 计算中间位置
        if (numbers[middle] <= target) {
            left = middle + 1; // 缩小左边界，继续查找右边
        } else {
            right = middle - 1; // 缩小右边界
        }
    }
    return (right >= 0 && numbers[right] == target) ? right : -1; // 检查是否找到
}

---

3.5 查找第一个大于目标值的位置

问题描述：

在一个升序数组中，查找第一个大于目标值的数字的位置。

示例：

输入数组 [1, 1, 2, 2, 3, 3, 3, 4]，目标值 3。 输出：索引 7（第一个大于 3 的数字是 4，位置为 7）。

代码：

public int findFirstGreater(int[] numbers, int target) {
    int left = 0;
    int right = numbers.length - 1;
    while (left <= right) {
        int middle = left + (right - left) / 2; // 计算中间位置
        if (numbers[middle] > target) {
            right = middle - 1; // 缩小右边界
        } else {
            left = middle + 1; // 缩小左边界
        }
    }
    return (left < numbers.length) ? left : -1; // 检查是否找到
}

4. 二分查找的核心要点

1. 明确查找目标：是否查找存在，或是某种边界值。
2. 定义搜索范围：设置初始的 left 和 right。
3. 调整范围逻辑：
   • left = middle + 1 表示向右缩小范围。
   • right = middle - 1 表示向左缩小范围。
4. 返回结果：根据题意返回查找到的索引或值。

典型应用对比

应用类型	返回值	更新逻辑
查找目标值	索引	if (numbers[middle] == target)
小于目标值的最后一个位置	索引	if (numbers[middle] < target)
目标值第一次出现的位置	索引	if (numbers[middle] >= target)
目标值最后一次出现的位置	索引	if (numbers[middle] <= target)
第一个大于目标值的位置	索引	if (numbers[middle] > target)

熟练掌握这些核心思想和分类应用，便可以轻松解决大多数查找问题。