桂帖 gui-forum

基本二分查找框架

int binarySearch(int[] nums, int target) {
    int left = 0;
    int 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. 时间复杂度：O(log n)

2. 空间复杂度：O(1)

3. 前提条件：输入数组必须是有序的

边界条件与特殊处理

1. 处理整数溢出

int mid = left + (right - left) / 2;  // 推荐写法
// 而不是
int mid = (left + right) / 2;         // 可能导致溢出

2. 处理空数组和单元素数组

if (nums == null || nums.length == 0) {
    return -1;
}
if (nums.length == 1) {
    return nums[0] == target ? 0 : -1;
}

3. 处理重复元素

当数组中有大量重复元素时，可能需要线性搜索：

if (nums[mid] == nums[left] && nums[mid] == nums[right]) {
    // 线性搜索
    for (int i = left; i <= right; i++) {
        if (nums[i] == target) return i;
    }
    return -1;
}

4. 终止条件选择

• • 找明确目标值用left <= right

  • 找最小值/最大值等用left < right

二分查找的应用场景

1. 有序集合的快速查找

2. 数值计算中的近似解（如求平方根）

3. 寻找边界值或极值

4. 解决一些优化问题（如最小化最大值问题）

常见错误与调试技巧

1. 循环条件错误：

   • 使用while (left <= right)而不是while (left < right)

   • 除非有特殊需求（如找最小值）

2. 边界更新错误：

   • 确保在每次迭代中缩小搜索范围

   • left = mid + 1或right = mid - 1

3. 调试技巧：

   • 打印left、right和mid的值

   • 检查循环终止条件

   • 验证边界条件（空数组、单元素数组等）