STL——二分查找函数

这里介绍STL中关于二分查找的各种方法，为了简单方便，我就采用最简单的数组来解释（对于数组，它的iterator就是他的地址，其他容器道理一样）

1.binary_search(arr[], arr[]+n, value)

这个方法是查找value值是否在arr数组中，只返回true或者是false

int array[8]={1,2,3,4,5,6,7,8};
    if(binary_search(array,array+8,5)){
    	cout<<"找到5元素！"<<endl;
	}
	else{
		cout<<"找不到5元素！"<<endl;
	}
	if(binary_search(array,array+8,10)){
    	cout<<"找到10元素！"<<endl;
	}
	else{
		cout<<"找不到10元素！"<<endl;
	} 

返回结果：

找到5元素！
找不到10元素！

2.lower_bound(arr[],arr[]+n,value)

该方法返回数组中第一个大于等于value的iterator，如果找不到则返回last，last超出数组的边界。

int array[8]={1,2,3,4,5,6,7,8};
    int pos=lower_bound(array,array+8,5)-array;
    cout<<pos<<endl;		//输出4，也就是原数组5的位置
    int pos2=lower_bound(array,array+8,10)-array;
    cout<<pos2<<endl;		//输出8

3.upper_bound(arr[],arr[]+n,value)

该方法返回数组中第一个大于value的iterator，如果找不到则返回last，last同上。

int array[8]={1,2,3,4,5,6,7,8};
    int pos=upper_bound(array,array+8,5)-array;
    cout<<pos<<endl;		//输出5，也就是原数组6的位置
    int pos2=upper_bound(array,array+8,10)-array;
    cout<<pos2<<endl;		//输出8

4.equal_range（arr[],arr[]+n,value）

该方法是上述2和3方法的结合，返回两个iterator，这里记作first和second。
first表示第一个等于value的iterator，second表示第一个大于value的iterator。

int array[12]={1,2,3,4,5,6,6,6,6,6,7,8};
    list<int>	lis_array(array,array+12);
    pair<list<int>::iterator,list<int>::iterator >	pos=equal_range(lis_array.begin(),lis_array.end(),6);
    for(auto i=pos.first;i!=pos.second;i++){
    	cout<<*i<<" ";			//输出6 6 6 6 6 
	}

以上就是简单地介绍这四种方法，如果大家有补充和纠正，可以留言噢！