本文主要是介绍查找和二分查找 lower_bound upper_bound，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
http://tianyanshentong.blog.51cto.com/3356396/1560237
//返回数组中等于key的值
1、当找大于等于key的第一个元素，或者查找小于等于key的最后一个元素时，
循环条件是 low < high，这和基本的二分查找不同，
但需要在循环退出的时候，判断是否满足条件；
2、如果是找最后一个满足条件的情况，
下限移动时不能用low=mid+1;而应该用low=mid；
此时，mid计算时应该用mid=（low+high+1）/2，
保证 最后low、high相差1时不会陷入死循环，
循环退出后，下限可能是结果；
3、如果是找第一个满足条件的情况，
移动时不能用 high=mid-1；而应该用high=mid；
此时，mid计算时还是用mid=（low+high）/2，想想为什么？
循环退出后，上限可能是结果
int binary_search(int a[],int low,int high,int key){while(low<=high) {int mid=(low+high)/2;if (a[mid]==key) return mid;else if (a[mid]>key) high=mid-1;else low=mid+1;//a[mid] < key}return -1;
}//返回数组中最后一个小于等于key的值
int binary_up_bound(int a[],int low,int high,int key){while (low<high){int mid=(low+high+1)/2;if (a[mid]>key)high=mid-1;else low=mid;//a[mid]<=key}if (a[low]<=key) return low;else return -1;
}
//返回数组中第一个大于等于key的值
int binary_low_bound(int a[],int low,int high,int key){while (low<high){int mid=(low+high)/2;if (a[mid]<key)low=mid+1;else high=mid;//a[mid]>=key}if (a[high]>=key)return high;else return -1;
}
int main(){int a[]={1,2,3,4,6,6,7,8};int pos=-1;int key=0;cout<<"intput key:";cin>>key;pos=binary_search(a,0,N-1,key);cout<<"binary search result:"<<pos<<endl;pos=0;pos=binary_up_bound(a,0,N-1,key);cout<<"binary search result:"<<pos<<endl;pos=0;pos=binary_low_bound(a,0,N-1,key);
cout<<"binary search result:"<<pos<<endl;
}http://www.cnblogs.com/wanghetao/archive/2012/05/22/2513910.html
//这篇是专注讲怎样用lower_bound 和 upper_bound
C++ STLiterator lower_bound( const key_type &key );iterator upper_bound( const key_type &key );
函数作用iterator lower_bound( const key_type &key ): 返回一个迭代器，指向键值>=key的第一个元素。iterator upper_bound( const key_type &key ): 返回一个迭代器，指向键值>key的第一个元素。lower_bound: 返回>=对象的第一个位置
lower_bound(2)=3
lower_bound(3)=3
目标对象存在即为目标对象的位置,不存在则为后一个位置.
upper_bound 返回>对象的第一个位置
upper_bound(2)=3,upper_bound(3)=4 无论是否存在都为后一个位置
lower_bound()函数
第一个版本
template< class ForwardIterator, class Type >
ForwardIterator
lower_bound(ForwardIterator first,ForwardIterator last, const Type &value );
这里的forwardIterator可以理解成一个数组，first表示数组中的某一个区间开始查找第一个位置，last则是最后一个，const Type &value这个可以理解成想查找的一个元素
也可以这样写
pos=lower_bound(lis+1,lis+len+1,num[i])-lis;
lis 表示的是一个数组，这里是指从数组的第一个位置到最后一个位置，查找num[i]这个元素
第二个版本：
template
函数介绍
lower_bound()返回一个iterator 它指向在[first,last)标记的有序序列中可以插入value，而不会破坏容器顺序的第一个位置，而这个位置标记了一个大于等于value 的值。
例如，有如下序列：
ia[]={12,15,17,19,20,22,23,26,29,35,40,51};
用值21调用lower_bound(),返回一个指向22的iterator。
用值22调用lower_bound(),也返回一个指向22的iterator。
第一个版本使用底层的<(小于)操作符，第二个版本根据comp进行排序和比较。注意事项
调用lower_bound之前必须确定序列为有序序列，否则调用出错。第一个版本排序根据底层的 <(小于)操作符，第二个版本根据comp进行排序。
http://www.cnblogs.com/mfryf/archive/2012/09/05/2672700.html
//这个讲的很详细，讨论了6中查找的STL中的函数，讲得很长，得细心看
count,find,binary_search,lower_bound,upper_bound,equal_range
首先,选择查找算法时，区间是否排序是一个至关重要的因素。
可以按是否需要排序区间分为两组:
A. count,find
B. binary_search,lower_bound,upper_bound,equal_range
A组不需排序区间， B组需要排序区间。
当一个区间被排序，优先选择B组，因为他们提供对数时间的效率。而A则是线性时间。
另外A组B组所依赖的查找判断法则不同，A使用相等性法则(查找对象需要定义operator==), B使用等价性法则(查找对象需要定义operator<,必须在相等时返回false)。
A组的区别
count:计算对象区间中的数目。
find:返回第一个对象的位置。
查找成功的话，find会立即返回，count不会立即返回（直到查找完整个区间），此时find效率较高。
因此除非是要计算对象的数目，否则不考虑count。
B组的区别
{1，3，4，5，6}
binary_search：判断是否存在某个对象
lower_bound: 返回>=对象的第一个位置
lower_bound(2)=3
lower_bound(3)=3
//目标对象存在即为目标对象的位置,不存在则为后一个位置.
upper_bound: 返回>对象的第一个位置
upper_bound(2)=3
upper_bound(3)=4
//无论是否存在都为后一个位置.
equal_bound: 返回由lower_bound和upper_bound返回值构成的pair,也就是所有等价元素区间。
equal_bound有两个需要注意的地方:
1. 如果返回的两个迭代器相同，说明查找区间为空，没有这样的值
Section II binary search in STL
如果在C++ STL容器中包含了有序的序列，STL提供了四个函数进行搜索，他们是利用二分查找实现的(Binary search).
假定相同值的元素可能有多个
lower_bound 返回第一个符合条件的元素位置
upper_bound 返回最后一个符合条件的元素位置
equal_range 返回所有等于指定值的头/尾元素的位置，其实就是lower_bound和upper_bound
binary_search 返回是否有需要查找的元素。
这篇关于查找和二分查找 lower_bound upper_bound的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
