二分查找模板 low_bound、upper_bound

简介: 二分查找模板 low_bound、upper_bound

下标从1开始,返回长度为n的数组a中最后一个等于key的下标

int search1(int a[], int n, int key){
   
    int l = 1, r = n, ans;
    while (l <= r){
   
        int mid = (l + r) / 2;
        if (a[mid] <= key){
   
            l = mid + 1;
            ans = mid;
        }else{
   
            r = mid - 1;
        }
    }
    return a[ans]==key ? ans : -1;
}

下标从1开始,返回长度为n的数组a中最第一个等于key的下标

int search2(int a[], int n, int key){
   
    int l = 1, r = n, ans;
    while (l <= r){
   
        int mid = (l + r) / 2;
        if (a[mid] < key){
   
            l = mid + 1;
        }else{
   
            r = mid - 1;
            ans = mid;
        }
    }
    return a[ans] == key ? ans, -1;
}

low_bound、upper_bound

#include <iostream>
#include <algorithm>
using namespace std;

int main(){
   
    int a[11]={
   0,1,2,3,4,4,4,5,6,7,8};
    //lower_bound(begin, end, key)
    //二从数组的begin位置到end-1位置二分查找第一个大于或等于key的数字,
    //找到返回该数字的地址,不存在则返回end。
    int pos = lower_bound(a+1, a+10+1, 4) - a;
    cout<<pos<<endl;

    //upper_bound(begin, end, key)
    //从数组的begin位置到end-1位置二分查找第一个大于key的数字,
    //找到返回该数字的地址,不存在则返回end。
    int pos2 = upper_bound(a+1, a+10+1, 4) - a;
    cout<<pos2<<endl; 
    return 0;
}
相关文章
|
5月前
|
存储 算法
【洛谷 P1102】A-B 数对 题解(向量+lower_bound+upper_bound)
这是一个编程题目,要求计算给定正整数序列中满足 \( A - B = C \) 的数对个数。输入包含两行:正整数 \( N \) 和 \( C \),以及一串正整数。输出是满足条件的数对数量。使用排序和二分查找优化算法,代码中给出了 AC 解决方案。样例输入为 \( N=4, C=1 \),序列 \( 1, 1, 2, 3 \),输出为 \( 3 \)。数据范围:\( 1 \leq N \leq 2 \times 10^5 \),\( 0 \leq a_i &lt; 2^{30} \),\( 1 \leq C &lt; 2^{30} \)。
36 0
|
机器学习/深度学习
LeetCode-2055 蜡烛之间的盘子 及库函数 lower_bound 和 upper_bound学习使用
LeetCode-2055 蜡烛之间的盘子 及库函数 lower_bound 和 upper_bound学习使用
Leetcode Find Minimum in Rotated Sorted Array 题解
对一个有序数组翻转, 就是随机取前K个数,移动到数组的后面,然后让你找出最小的那个数,注意,K有可能是0,也就是没有翻转。
45 0
|
算法
Light oj 1082 - Array Queries(区间最小值)
这里只要知道这种算法即可,因为数据量过大,都编译不通过,不过思想算法没有任何问题。
30 0
|
索引
LeetCode 416. Partition Equal Subset Sum
给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集,使得两个子集的元素和相等。
105 0
LeetCode 416. Partition Equal Subset Sum
|
开发工具
15分钟带你了解lower_bound和upper_bound
🍀理解,学会lower_bound和upper_bound原理及其用法
277 0
15分钟带你了解lower_bound和upper_bound
Leetcode-Medium 416. Partition Equal Subset Sum
Leetcode-Medium 416. Partition Equal Subset Sum
120 0