二分查找

0 基本型

对于一个没有重复元素的有序数组，查找某个元素。
我最常用的板子是左闭右开[l, r)：

int biSearch(vector<int>& nums, int target) {
    int l = 0, r = nums.size();
    while (l < r) {
        int mid = (l + r) / 2;
        if (target == nums[mid])
            return mid;
        if (target > nums[mid])
            l = mid + 1;
        else
            r = mid;
    }
    return -1;   // not found
}

1 lower_bound()

数组有重复元素，查找满足\(x>=target\)的最小\(x\)的index：

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

可变形为查找最后一个小于\(target\)的数：即\(l-1\)。

2 upper_bound()

数组有重复元素，查找满足\(x>target\)的最小\(x\)的index：

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

可变形为查找最后一个小于\(target\)的数：即\(l-1\)。

二分查找

原文：https://www.cnblogs.com/EIMadrigal/p/12179993.html