binary_search

lower_bound的实现

int lower_bound(int *arr, int len, int key){
  //-1是取不到的值，而len则可以取到(此时key大于数组中所有的值)
  int lb = -1, ub = len;

  while(ub - lb > 1){
    int mid = (ub + lb) /2;

    if(arr[mid] < key){
      lb = mid；
    }else{
      ub = mid;
    }
  }

  return ub;
}

上面为什么要用上界了，因为在二分过程中，改变下界的条件是arr[mid] < key，此时说明key在右半部分，常规的做法是将下界变为(mid 或者 mid + 1),而这两个值不一定有效

求得是arr[i] >= key的最 注意得到的是排序好的数组中大于或等于key的数的下标

当arr[mid] < key时，一定取不到mid，所以lb = mid，lb在变化的过程中始终取不到

当arr[mid] > key时，有可能取到mid,

同样,当arr[mid] == key时，有可能取到mid(数组中有重复的元素，多个key)

另外的二分写法

int lb = value1,ub = value2;连个均是可以取到的值

while(lb < ub){
  int mid = (ub + lb) >>1;

  if()
    lb = mid + 1;    //此处一定要是mid+1,否则会导致死循环（当只有两个元素进行二分的时候，mid刚好在第一个元素）
   else
     ub = mid;
}