C++ lower_bound 和upper_bound

二分查找的函数有 3 个:

1.lower_bound(起始地址,结束地址,要查找的数值) 返回的是数值 第一个 出现的位置。

2.upper_bound(起始地址,结束地址,要查找的数值) 返回的是数值 最后一个 出现的位置。

3.binary_search(起始地址,结束地址,要查找的数值)  返回的是是否存在这么一个数,是一个bool值。

举例:

数组 a(下标从1开始) : 1  2  3  3  3  4  5

查找 3 :

int position1 = lower_bound(a+,a+n,) - a; //position1 = 3
int position2 = upper_bound(a+,a+n,) - a; //position2 = 5 

需要注意的是:如果数组中没有找到所求元素,函数就会返回一个假想的插入位置。

int a[] = {,,,,,};
int position1 = lower_bound(a+,a+,) - a;
int position2 = upper_bound(a+,a+,) - a;
cout << position1 << endl;
cout << position2 << endl;
// position1 = position2 = 3

还有二分查找的首要条件是数列有序!

上一篇:稀疏表示(sparse representation)和字典学习


下一篇:使用CompletionService结合ExecutorService批处理任务