704.md

704. 二分查找

红蓝染色法

l和r指针指向边界，左区间为蓝色，右区间为红色。满足条件移动指针，更新染色区域。循环结束时l指向蓝边界，r指向红边界。

搜索区间：(l,r)。

l = -1, r = N
while (l + 1 != r) {
    m = (l + r) / 2;
    if (isBlue(m)) {
        l = m;
    } else {
        r = m;
    }
    return l or r;
}

如果搜索区间：[l, r]。

l = 0, r = N-1
while (l != r) {
    m = (l + r) / 2;
    if (isBlue(m)) {
        l = m + 1;
    } else {
        r = m - 1;
    }
    // l指向红边界，r指向蓝边界
    return l or r;
}

二分查找

左区间小于等于target，右区间大于target。

时间复杂度：O(logn)。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > target) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return -1;
    }
};