欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【二分查找】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
请按任意键继续. . .