本文为senlie原创，转载请保留此地址：

lower_bound(应用于有序区间)

--------------------------------------------------------------------------------------------------------------------------

描写叙述：二分查找，返回一个迭代器指向每个"不小于 value "的元素，

或 value 应该存在的位置

思路：

1.循环直到区间长度为 0 

2.假设 *middle < value，在后半段继续查找

3.假设 *middle >= value，在前半段继续查找 (等于的时候也会继续在前半段查找，所以能保证找到的是 lower bound)

源代码：

template 
     
      inline ForwardIterator lower_bound(ForwardIterator first, ForwardIterator last,                                   const T& value) {  return __lower_bound(first, last, value, distance_type(first),                       iterator_category(first));}// forward_iterator_tag 版本号template 
      
       ForwardIterator __lower_bound(ForwardIterator first, ForwardIterator last,                              const T& value, Distance*,                              forward_iterator_tag) {  Distance len = 0;  distance(first, last, len);  Distance half;  ForwardIterator middle;  while (len > 0) {    half = len >> 1;    middle = first;    advance(middle, half); // 由于仅仅是 ForwardIterator，不能採用 middle = middle + half 的方式     if (*middle < value) {      first = middle;      ++first;      len = len - half - 1;    } // 由于 *middle >= value 时，会在前半段继续查找。所以终于找到的是 lower bound    else      len = half;  }  return first;}// random_access_iterator_tag 版本号template 
       
        RandomAccessIterator __lower_bound(RandomAccessIterator first,                                   RandomAccessIterator last, const T& value,                                   Distance*, random_access_iterator_tag) {  Distance len = last - first; // 整个区间长度  Distance half;  RandomAccessIterator middle;  while (len > 0) {    half = len >> 1; //除以2    middle = first + half;    if (*middle < value) {       first = middle + 1;      len = len - half - 1; // -half-1 是由于前面那段有first指向的元素和half指向的区间     }    else //为什么这种代码能保证找到的是 lower bound ？--> 由于小于等于都是到前面一段区间查找，所以最后找到的一定是 lower bound      len = half;  }  return first;}
       
      
     

演示样例：

int main(){  int A[] = { 1, 2, 3, 3, 3, 5, 8 };  const int N = sizeof(A) / sizeof(int);  for (int i = 1; i <= 10; ++i) {    int* p = lower_bound(A, A + N, i);    cout << "Searching for " << i << ".  ";    cout << "Result: index = " << p - A << ", ";    if (p != A + N)      cout << "A[" << p - A << "] == " << *p << endl;    else      cout << "which is off-the-end." << endl;  }}/*The output is:Searching for 1.  Result: index = 0, A[0] == 1Searching for 2.  Result: index = 1, A[1] == 2Searching for 3.  Result: index = 2, A[2] == 3Searching for 4.  Result: index = 5, A[5] == 5Searching for 5.  Result: index = 5, A[5] == 5Searching for 6.  Result: index = 6, A[6] == 8Searching for 7.  Result: index = 6, A[6] == 8Searching for 8.  Result: index = 6, A[6] == 8Searching for 9.  Result: index = 7, which is off-the-end.Searching for 10.  Result: index = 7, which is off-the-end.*/