bin_search()和lower_bound()对比测试

#include<bits/stdc++.h>
using namespace std;
#define MAX 100 //试试10000000
#define MIN -100
int a[MAX];                     //大数组a[MAX]应定义为全局
unsigned long ulrand(){         //生成一个大随机数     
  return (
       (((unsigned long)rand()<<24) & 0xFF000000ul)   //左移位>>4，数字进1位（十六进制）
    |  (((unsigned long)rand()<<12) & 0x00FFF000ul)   
    |  (((unsigned long)rand()    ) & 0x00000FFFul)
  );
}
int bin_search(int *a, int n, int x){                 //a[0]～a[n-1]是有序的
  int left = 0, right = n; //不是 n-1
  while (left < right) {
    int mid = left+(right-left)/2;                    //int mid = (left+ right)>>1;
    if (a[mid] >= x) right = mid;
    else left = mid + 1;
  }
  return left; //特殊情况：如果最后的a[n-1] < key，left = n
}
int main(){
  int n = MAX;
  srand(time(0));                                 //时间作为随机种子，time(0)返回从1997-1-1到现在的秒数
  while(1){
    for(int i=0; i< n; i++)                       //产生[MIN, MAX]内的随机数，有正有负
      a[i] = ulrand() % (MAX-MIN + 1) + MIN;      //返回的大随机数取余区间长度，再加上下限放进数组
    sort(a, a + n );                              //排序，a[0]~a[n-1]
    int test = ulrand() % (MAX-MIN + 1) + MIN;    //产生一个随机的x
    int ans = bin_search(a,n,test);
    int pos = upper_bound(a,a+n,test)-a; 
    //比较bin_search()和lower_bound()的输出是否一致：
    if(ans == pos) cout << "!";                   //正确  
    else { cout << "wrong"; break;}               //有错，退出
  }
}

笔记：通过lower_bount()函数的证明，确定了程序里的bin_search()函数的正确性。bin_search()函数通过 mid = left + (right – left) / 2 来实现后继的二分法