int binarysearch1(int a[],int n,int x) 
{ 
 int l,u,m; 
 l=0;u=n; 
 while(l<u) 
 { 
  m=l+((u-l)>>1); 
  if(x<a[m]) 
   u=m; 
  else if(x==a[m]) 
   return m; 
  else 
   l=m+1; 
 } 
 return -1; 
} 

int binarysearch1(int a[],int n,int x) 
{ 
 int l,u,m; 
 l=0;u=n-1; 
 while(l<=u) 
 { 
  m=l+((u-l)>>1); 
  if(x<a[m]) 
   u=m-1; 
  else if(x==a[m]) 
   return m; 
  else 
   l=m+1; 
 } 
 return -1; 
} 

int binarysearch2(int *a,int n,int x) 
{ 
 int *l,*u,*m; 
 l=a;u=a+n-1; 
 while(l<=u) 
 { 
  m=l+((u-l)>>1); 
  if(x<*m) 
   u=m-1; 
  else if(x==*m) 
   return m-a; 
  else 
   l=m+1; 
 } 
 return -1; 
} 

int binarysearch2(int *a,int n,int x) 
{ 
 int *l,*u,*m; 
 l=a;u=a+n; 
 while(l<u) 
 { 
  m=l+((u-l)>>1); 
  if(x<*m) 
   u=m; 
  else if(x==*m) 
   return m-a; 
  else 
   l=m+1; 
 } 
 return -1; 
} 

int binarysearch3(int a[],int l,int u,int x) 
 
int m=l+((u-l)>>1); 
if(l<=u) 
{ 
 if(x<a[m]) 
  return binarysearch3(a,l,m-1,x); 
 else if(x==a[m]) 
  return m; 
 else 
  return binarysearch3(a,m+1,u,x); 
} 
return -1; 

int binarysearch4(int a[],int n,int x) 
{ 
 int l,u,m; 
 int flag=-1; 
 l=0;u=n; 
 while(l<u) 
 { 
  m=l+((u-l)>>1); 
  if(x<a[m]) 
   u=m; 
  else if(x==a[m]) 
   flag=u=m; 
  else 
   l=m+1; 
 } 
 return flag; 
} 

int binarysearch4(int a[],int n,int x) 
{ 
 int l,u,m; 
 l=-1;u=n; 
 while(l+1<u) 
 { 
  m=l+((u-l)>>1); 
  if(a[m]<x) 
   l=m; 
  else 
   u=m; 
 } 
 return (u>=n||a[u]!=x)?-1:u; 
} 

#include <iostream> 
#include <cassert> 
#include <algorithm> 
#include <ctime> 
using namespace std; 
 
int calmid(int l,int u) { return l+((u-l)>>1); } 
int binarysearch1(int a[],int n,int x); 
 
#define bs1 binarysearch1 
 
int main() 
{ 
 long start,end; 
 start=clock(); 
 
 int a[9]={-2147483648,-13,-10,-5,-3,0,1,400,2147483647}; 
 //中值下标计算的测试 
 assert(calmid(0,1)==0); 
 assert(calmid(0,2)==1); 
 assert(calmid(1000000,2000000)==1500000); 
 assert(calmid(2147483646,2147483647)==2147483646); 
 assert(calmid(2147483645,2147483647)==2147483646); 
 
 //冒烟测试 
 assert(bs1(a,9,0)==5); 
 assert(bs1(a,9,1)==6); 
 assert(bs1(a,9,2)==-1); 
 
 //边界测试 
 assert(bs1(a,0,1)==-1);       //0个元素 
 assert(bs1(a,1,-2147483648)==0);  //1个元素 成功 
 assert(bs1(a,1,-2147483647)==-1);  //1个元素 失败 
 
 assert(bs1(a,9,-2147483648)==0);  //首个元素 
 assert(bs1(a,9,-3)==4);       //中间元素 
 assert(bs1(a,9,2147483647)==8);  //末尾元素 
 
 //自动化测试 
 int b[10000]; 
 int i,j; 
 for(i=0;i<10000;i++) 
 { 
  b[i]=i*10; 
  for(j=0;j<=i;j++) 
  { 
   assert(bs1(b,i+1,j*10)==j); 
   assert(bs1(b,i+1,j*10-5)==-1); 
  } 
 } 
 
 //自动化测试 引入随机数 
 srand(time(0)); 
 for(i=0;i<10000;i++) 
 { 
  b[i]=rand()00000; 
  sort(&b[0],&b[i]); 
  for(j=0;j<=i;j++) 
  { 
   int x=rand(); 
   int k=bs1(b,i+1,x); 
   if(k!=-1) 
    assert(b[k]==x); 
  } 
 } 
 
 end=clock(); 
 cout<<(end-start)/1000.0<<'s'<<endl; 
 return 0; 
} 

//a为排好序的数组，n为数组的大小，x为指定元素 
int binarySearch(int a[], int n, int x) 
{ 
 int left = 0, right = n-1, middle = 0; 
 int tmp = 0; 
 while(left <= right) 
 { 
   middle = (left + right)/2; 
   tmp = a[middle]; 
   if(x < tmp) right = middle - 1; 
   else if(x > tmp) left = middle + 1; 
   else return middle; 
 } 
 return -1; 
}