二分查找算法和实例介绍

1. 核心思想

二分算法是一种高效的搜索算法，适用于有序数组，通过分治策略逐步缩小搜索范围。其核心思想是：

• 将数组分为两半，比较目标值与中间元素的大小关系；
• 根据比较结果，决定继续在左半部分或右半部分搜索；
• 重复此过程，直到找到目标值或确定其不存在。

2. 使用前提

• 数组必须有序（升序或降序）。
• 适用于静态数据（无需频繁插入/删除），因动态数据维护有序性成本较高。

3. 算法步骤

以升序数组为例，查找目标值 target：

1. 初始化：定义两个指针 low（起始位置）和 high（结束位置）。
   • 通常 low = 0，high = 数组长度 - 1。
2. 循环条件：当 low <= high 时继续循环。
3. 计算中间位置：
   mid = (low + high) / 2（或 mid = low + (high - low) / 2 避免溢出）。
4. 比较中间元素：
   • 若 arr[mid] == target：返回索引 mid。
   • 若 arr[mid] > target：目标在左侧，更新 high = mid - 1。
   • 若 arr[mid] < target：目标在右侧，更新 low = mid + 1。
5. 结束条件：若 low > high，说明未找到目标值，返回 -1。

4. 时间复杂度

• 时间复杂度：O(log n)，其中 n 为数组长度。
  • 每次比较可排除一半数据，效率远高于线性查找的 O(n)。
• 空间复杂度：O(1)（原地查找，无需额外空间）。

5. 应用场景

• 基础查找：在有序数组中快速定位目标值。
• 变体问题：
  • 查找第一个大于等于/小于等于目标值的位置（lower_bound/upper_bound）。
  • 计算目标值的出现次数。
• 优化问题：如求解函数极值、最小化最大值等问题。

6. 常见实现模板

模板1：标准二分查找

public static int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2; // 防溢出
        if (arr[mid] == target) return mid;
        else if (arr[mid] > target) high = mid - 1;
        else low = mid + 1;
    }
    return -1;
}

模板2：查找左边界（lower_bound）

public static int lowerBound(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] >= target) high = mid;
        else low = mid + 1;
    }
    return low;
}

7. 注意事项

1. 死循环问题：
   • 循环条件需与 low/high 更新方式匹配。例如：
     • 若使用 while (low < high)，则需确保每次循环都能缩小范围。
2. 中间值计算：
   • 使用 mid = low + (high - low) / 2 避免整数溢出（尤其在大型数组中）。
3. 边界处理：
   • 需明确 low/high 的更新逻辑（是否包含 mid），防止漏掉可能解。

8. 实例演示

假设数组为 [1, 5, 10, 19, 21, 28, 30, 31, 78, 92]，查找 28：

1. 初始 low=0, high=9 → mid=4, arr[4]=21 < 28 → 更新 low=5。
2. low=5, high=9 → mid=7, arr[7]=31 > 28 → 更新 high=6。
3. low=5, high=6 → mid=5, arr[5]=28 == 28 → 返回索引 5。

9. 局限性

• 仅适用于有序数据：若数据无序，需先排序（时间复杂度 O(n log n)）。
• 不适用于链表：链表无法高效随机访问中间元素。

总结

二分算法是高效查找的核心工具，但需注意实现细节（如边界处理、死循环）。掌握其思想及常见变体（如左/右边界查找），可快速解决大量实际问题。