「LeetCode」lower_bound() 和 upper_bound()

2020-05-08
摘要: 本文介绍了 C++ 中 lower_bound() 和 upper_bound() 函数。

lower_bound() 和 upper_bound()#

它们都是利用二分查找的方法在一个排好序的数组中进行查找。因此复杂度为 $O(\log(N))$。

升序数组#

lower_bound(begin, end, num) 返回 $[\mathrm{begin},\mathrm{end})$ 中第一个大于或等于 num 的数字。若找到返回该数字的地址(或迭代器),不存在则返回 end。通过返回的地址(或迭代器)减去起始地址(或迭代器) begin,可以得到该数字在数组中的下标。

upper_bound(begin, end, num) 返回 $[\mathrm{begin},\mathrm{end})$ 中第一个大于 num 的数字。若找到返回该数字的地址(或迭代器),不存在则返回 end。通过返回的地址(或迭代器)减去起始地址(或迭代器) begin,可以得到该数字在数组中的下标。

降序数组#

我们需要新增一个参数 greater<T>(),其中 T 为数组中元素的类型。

lower_bound(begin, end, num, greater<T>()) 返回 $[\mathrm{begin},\mathrm{end})$ 中第一个小于或等于 num 的数字。若找到返回该数字的地址(或迭代器),不存在则返回 end。通过返回的地址(或迭代器)减去起始地址(或迭代器) begin,可以得到该数字在数组中的下标。

upper_bound(begin, end, num, greater<T>()) 返回 $[\mathrm{begin},\mathrm{end})$ 中第一个小于 num 的数字。若找到返回该数字的地址(或迭代器),不存在则返回 end。通过返回的地址(或迭代器)减去起始地址(或迭代器) begin,可以得到该数字在数组中的下标。

自定义比较函数#

第一种是重载结构体的 < 运算符即可。另外可以选择自定义函数:

bool cmp(node a, node b)
{
    return a.b == b.b ? a.c < b.c : a.b < b.b;
}

upper_bound(a + 1, a + 11, node(i, 10), cmp);

示例#

数组#

int num1[] = {1, 2, 4, 7, 7, 15, 34};

int pos1 = lower_bound(num1, num1 + 7, 7) - num1; // 3
int pos2 = upper_bound(num1, num1 + 7, 7) - num1; // 5

int num2[] = {34, 15, 7, 7, 4, 2, 1};

int pos3 = lower_bound(num2, num2 + 7, 7, greater<int>()) - num2; // 2
int pos4 = upper_bound(num2, num2 + 7, 7, greater<int>()) - num2; // 4

vector#

vector<int> num1 = {1, 2, 4, 7, 7, 15, 34};

int pos1 = lower_bound(num1.begin(), num1.end(), 7) - num1.begin(); // 3
int pos2 = upper_bound(num1.begin(), num1.end(), 7) - num1.begin(); // 5

vector<int> num2 = {34, 15, 7, 7, 4, 2, 1};

int pos3 = lower_bound(num2.begin(), num2.end(), 7, greater<int>()) - num2.begin(); // 2
int pos4 = upper_bound(num2.begin(), num2.end(), 7, greater<int>()) - num2.begin(); // 4

怎么实现一个 lower_bound() 和 upper_bound()?#

我们动手实现一下这两个二分查找函数,因为有时候我们需要手动实现这样的二分查找。

升序数组#

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

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

降序数组#

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


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