STL中二分查找

偶然遇到了一些问题，记录一下

头文件#include <algorithm>

1.binary_search：查找某个元素是否出现。

函数原型：BOOL lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)

函数功能：在数组中以二分法检索的方式查找，若在数组(要求数组元素非递减)中查找到val元素则真，若查找不到则返回值为假。

2.lower_bound：查找第一个大于或等于某个元素的位置。

函数原型：ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)

函数功能：要求数组已排序，返回一个非递减序列[first, last)中的第一个大于等于值val的位置（迭代器）。如果所有元素都小于val，则返回last的位置，该位置可能越界，为容器的end()。

3.upper_bound：查找第一个大于某个元素的位置。

函数原型： ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)

函数功能：要求数组已排序，返回一个非递减序列[first, last)中第一个大于val的位置（迭代器）。如果所有元素都小于val，则返回last的位置，该位置可能越界，为容器的end()。

举个例子：

std::vector<int> vec{1,2,3,4,4,4,5,6};

std::vector<int>::iterator it1 = std::lower_bound(vec.begin(), vec.end(), 4);

it1表示第一个数值为4 的位置

std::vector<int>::iterator it2 = std::upper_bound(vec.begin(), vec.end(), 4);

it2表示数值为5的位置

 

基础用法应该很容易理解，那么如果是二维数组呢？

假设 一个行和列都是递增的二维数组，std::vector<std::vector<int>> vec2 = { {1,2,3}, {2,3,4}, {3,4,5} };

函数的第三个参数应该是一维数组，如果定义函数 bool Find(int target, std::vector<std::vector<int> > array)意在寻找target是否存在于该数组中，那么函数可以这么写（函数写的有问题，只是想说明写法而已）：

bool Find(int target, std::vector<std::vector<int> > array) {
    //...这里省略前置判断
    std::vector<std::vector<int>>::iterator it3 = std::upper_bound(array.begin(), array.end(), std::vector<int>{ target });
    //...这里省略it3判断
    return std::binary_search(it3->begin(), it3->end(), target);
}

调用Find(2, vec2);  那么it3会返回第二行，也就是{2,3,4}。

 

相同地，如果要找的是结构体，那么也要构造结构体。

假设一个结构体

struct STU
{
	int id;
	int age;
	STU() {}
	STU(int a, int b) :id(a), age(b) {}
	bool operator<(const STU m)const { //定义比较方式，很重要一定要写
		return id < m.id;
	}
};

int main()
{
    std::vector<STU> vec2 = { {1,60},{2,70},{3,80} };
	std::vector<STU>::iterator it4 = std::upper_bound(vec2.begin(), vec2.end(), STU(2, 0));
	std::cout << it4->id << " " << it4->age << std::endl;	//输出3 80
}

    结构体里必须重载比较运算符，因为是根据id值来排序，因此构造STU第二个参数可以随便写，第一个参数是要找的基准。