【二分查找】c++ 中 stl 直接调用二分搜索函数
程序员文章站
2022-03-14 09:58:03
...
在<algorithm>中有直接实现二分搜索的函数,这样解决一些简单问题时,就不必再手撕算法了。
1. binary_search(arr[],arr[]+size , index)
二分查找,其中,arr[] 表示数组首地址,size表示元素个数,index则表示查找的元素,首要的一点是数组必须是有序的,并且一定是从小到大的,非递减的。可以看出 size 和sort 等函数的使用方法都是一样的,都是到最后元素的下一位
2. lower_bound(arr[],arr[]+size,index)
查找在范围内大于或等于index的数组元素中第一个元素的地址,相当于一个指针值
3.upper_bound(arr[],arr[]+size,index)
查找在范围内大于index的数组元素中第一个元素的地址,相当于一个指针值。暂时还没找到找出第一个小于index的数组元素的函数。
一些实验:
#include <algorithm>
#include <iostream>
#include<functional>
#include<vector>
using namespace std;
int main()
{
//bool 型包括true与false,可以被提升为int型
//true 和 false 打印出来都是 int 型的
bool t = true;
cout << "bool t = true ,t = " << t << endl;
cout << "t + 3 = " << t + 3 << endl;
cout << "ture (实际就是1): " << true << endl;
cout << "flase(实际就是0); " << false << endl;
cout << "true + 3 = " << true + 3 << endl;
cout << "false + 1 = " << false + 1 << endl;
//binary_search()的使用,只返回 true 或 false,即 1 或 0
int a[10] = { 1,2,3,4,5 };
int p = binary_search(a, a + 5, 6);
cout << "int p = binary_search(a, a + 5, 6),p = " << p << endl;
if (binary_search(a, a + 5, 3))
cout << "binary_search(a, a + 5, 3)成功找到 3 !" << endl;
else
cout << "binary_search(a, a + 5, 3)没有找到3 !" << endl;
//实验在数组中取一个范围去找,2是这个范围中元素的个数,不包括 3
//因为 a + 2 是最后一个元素的下一位
if (binary_search(a, a + 2, 3))
cout << "binary_search(a, a + 2, 3)成功找到 3 !" << endl;
else
cout << "binary_search(a, a + 2, 3)没有找到3 !" << endl;
//a + 3 是从4开始的,a + 0 则是从1开始的,a + 3 + 2, 2是 size
if(binary_search(a + 3, a + 5, 3))
cout << "binary_search(a + 3, a + 5, 3)成功找到 3 !" << endl;
else
cout << "binary_search(a + 3, a + 5, 3)没有找到3 !" << endl;
//lower_bound()的使用,得到的是一个地址值,要经过处理才能得到
//从这里也可以看出a + n 得到的是第 n 个数组元素的地址
//这里的pos实际是该数组元素在数组中的下标
int pos1 = lower_bound(a, a + 5, 0.5) - a;
cout << "int pos1 = lower_bound(a, a + 5, 0.5) - a : " << pos1 << endl;
//获得该数组元素的具体值
int value1 = *lower_bound(a, a + 5, 0.5);
cout << "int value1 = *lower_bound(a, a + 5, 0.5): " << value1 << endl;
//没有大于该值的则返回越界位置5,因为最大的下标是4
int pos2 = lower_bound(a, a + 5, 6) - a;
cout << "int pos2 = lower_bound(a, a + 5, 6): " << pos2 << endl;
//upper_bound()的使用,满足条件的是4,下标为3
int pos3 = upper_bound(a, a + 5, 3) - a;
cout << "int pos3 = upper_bound(a, a + 5, 3) - a : " << pos3 << endl;
//与lower_bound()的比较只有没有等于的关系,所以lower满足条件的是3,下标为2
int pos4 = lower_bound(a, a + 5, 3) - a;
cout << "int pos3 = upper_bound(a, a + 5, 3) - a: " << pos4 << endl;
return 0;
}
运行结果:
bool t = true ,t = 1
t + 3 = 4
ture (实际就是1): 1
flase(实际就是0); 0
true + 3 = 4
false + 1 = 1
int p = binary_search(a, a + 5, 6),p = 0
binary_search(a, a + 5, 3)成功找到 3 !
binary_search(a, a + 2, 3)没有找到3 !
binary_search(a + 3, a + 5, 3)没有找到3 !
int pos1 = lower_bound(a, a + 5, 0.5) - a : 0
int value1 = *lower_bound(a, a + 5, 0.5): 1
int pos2 = lower_bound(a, a + 5, 6): 5
int pos3 = upper_bound(a, a + 5, 3) - a : 3
int pos3 = upper_bound(a, a + 5, 3) - a: 2
请按任意键继续. . .
上一篇: 查找 二分查找
下一篇: 先进先出队列,优先级队列以及后进先出队列