二分的两种重要模型

STL中的两个函数

（详见：点我）： ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中第一个**大于**val的位置。

二分的两种重要模型：

二分最重要的：1.当前待查找序列，肯定包含目标元素 2.每次待查找序列的规模都会变小。 ①：0000001111111，寻找一个满足条件的最左； code：

int binary_search(int array[],int key) { int begin=0; int end=array.size(); while(begin<end) { int mid=begin+(end-begin)/2; if(a[mid]==1) end=mid; else begin=mid+1; } return begin; }

②：对于1111000000，寻找一个满足条件的最右； code……

int binary_search(int array[],int key) { int begin=0; int end=array.size(); while(begin<end) { int mid=begin+(end-begin+1)/2; if(a[mid]==1) begin=mid; //一定会变大 else end=mid-1; //一定会变小 } return begin; }