二分查找可视化 - O(log n)高效搜索

二分查找（Binary Search）是一种在有序数组中查找特定元素的算法。每次比较都能将搜索范围缩小一半，因此效率极高，时间复杂度为O(log n)。

算法步骤

初始化左指针left=0，右指针right=n-1
计算中间位置 mid = (left + right) / 2
比较 arr[mid] 与目标值：
相等：找到目标，返回mid
arr[mid] > target：目标在左半部分，right = mid - 1
arr[mid] < target：目标在右半部分，left = mid + 1
重复步骤2-3，直到 left > right（未找到）

时间与空间复杂度

情况	复杂度	说明
最好情况	O(1)	目标恰好在中间
平均/最坏	O(log n)	每次搜索范围减半
空间复杂度	O(1)	只需常数额外空间

为什么是O(log n)？因为每次比较后范围减半，最多需要 log₂(n) 次比较。对于100万个元素，最多只需约20次比较！

应用场景

在有序数组/列表中查找元素
数据库索引查询（B树、B+树）
查找插入位置（如bisect模块）
求解单调函数的零点
算法竞赛中的"二分答案"技巧

有序查找数据库索引二分答案数值计算

代码实现

def binary_search(arr, target):
    """二分查找 - 返回目标索引，未找到返回-1"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # 防止溢出
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1


def lower_bound(arr, target):
    """查找第一个 >= target 的位置"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return left


# 使用示例
arr = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(arr, 7))   # 输出: 3
print(binary_search(arr, 6))   # 输出: -1
print(lower_bound(arr, 6))     # 输出: 3 (第一个>=6的位置)

public class BinarySearch {
    
    /**
     * 二分查找 - 返回目标索引，未找到返回-1
     */
    public static int binarySearch(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 防止溢出
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1;
    }
    
    /**
     * 查找第一个 >= target 的位置
     */
    public static int lowerBound(int[] arr, int target) {
        int left = 0, right = arr.length;
        
        while (left < right) {
            int mid = (left + right) / 2;
            if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(binarySearch(arr, 7));  // 3
        System.out.println(binarySearch(arr, 6));  // -1
        System.out.println(lowerBound(arr, 6));   // 3
    }
}