二分查找（Binary Search）详解

二分查找是一种在有序数组中查找特定元素的高效算法，时间复杂度为 ​O(log n)​，比线性查找的 O(n) 快得多。

核心思想

​​"分而治之"​​ - 通过不断将搜索范围减半来快速定位目标值

算法特性

• ​前提条件​：数组必须是有序的（升序或降序）

• ​时间复杂度​：O(log n)

• ​空间复杂度​：O(1)（迭代实现）

• ​局限性​：仅适用于顺序存储结构（如数组），不适用于链表

算法步骤（升序数组为例）

1. ​初始化​：设置 low = 0，high = n-1（n为数组长度）

2. ​循环查找​：

   • 计算中点 mid = low + (high - low) / 2（防止整数溢出）

   • 如果 a[mid] == target，返回 mid

   • 如果 a[mid] < target，调整 low = mid + 1

   • 如果 a[mid] > target，调整 high = mid - 1

3. ​终止条件​：当 low > high 时未找到，返回 -1

代码实现（C#）

// 基础版（精确匹配）
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;
        if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

变体算法

1. 查找第一个等于目标的值

public int FirstEqual(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 left = mid + 1;
    }
    return (left < nums.Length && nums[left] == target) ? left : -1;
}

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

public int LastEqual(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 right = mid - 1;
    }
    return (right >= 0 && nums[right] == target) ? right : -1;
}

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

public int FirstGreaterOrEqual(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 left = mid + 1;
    }
    return left < nums.Length ? left : -1;
}

边界条件处理

1. ​空数组检查​：if (nums == null || nums.Length == 0) return -1;

2. ​整数溢出​：使用 mid = left + (right - left)/2 而非 (left + right)/2

3. ​重复元素​：根据需求选择基础版或变体算法

应用场景

1. 有序集合的快速查找

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

3. 数据库索引的B+树查找

4. 游戏中的猜数字AI

5. 系统设计中的日志时间戳查询

二分查找因其高效性，是算法面试中的高频考点，掌握其原理和各种变体对开发者至关重要。