沐杰自学练习

编程练习

二分查找

二分查找是一种在有序序列中快速定位目标位置的方法。它通过不断缩小候选区间，将查找的时间复杂度降低至 O(log n)。

以下是一个 C++ 示例，用于寻找升序数组中第一个大于等于目标值的元素位置：

#include <vector>

int first_ge(const std::vector<int>& a, int x) {
    int l = 0;
    int r = static_cast<int>(a.size());

    while (l < r) {
        int mid = l + (r - l) / 2;

        if (a[mid] < x) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return l;
}

对于数组 [1, 2, 2, 5]，查找目标值 2 时，返回位置 1；查找 3 时，返回位置 3。若没有符合条件的元素，则返回数组长度。

练习心得

明确边界，理解不变量

二分查找的重要细节不仅在于计算中点，更在于明确区间边界和循环不变量。采用左闭右开的 [l, r) 区间，可以让代码更容易检查并避免部分边界错误。