二分法查找数

时间:2021-02-22 22:10:20
#include <stdio.h>
int *bsearch(int *t,int n,int x)//利用不对称原理
{
int lo=0,hi=n;
while(lo<hi)
{
int mid=(hi+low)/2;
if(x<t[mid])
hi=mid;
else if(x>t[mid])
lo=mid+1;
else
return t+mid;
}
return NULL;
}
//优化去掉一些寻址符号,很多机器上的下标运算都比指针慢,t+mid的值可以存贮在一个局部变量中这样就不需要每次重新计算,从而减少一些寻址运算,用移位运算符代替除法和乘法
int *bsearch(int *t,int n,int x)
{
int lo=0,hi=n;
while(lo<hi)
{
int mid=lo+((hi-lo)>>2);//注意移位运算符比算术运算符的优先级要低,而且有些编译器不够智能,不会把除法实现成移位运算符,应为编译器真的的只是lo-hi肯那个为负,注意不可以用(mid=(lo+hi)》》2应为指针的加法是非法的)
int *p=t+mid;
if(x>*p)
lo=mid+1;
else if(x<*p)
hi=mid;
else
return p;
}
return NULL;
}
//但是二分法查找经常用对称边界来表达,应为用了对称边界来表达后,最后得到的程序看上去要整齐许多
int *bsearch(int *t,int n,int x)
{
int lo=0,hi=n-1;
while(lo<=hi)
{
int mid=(hi+lo)/2;
if(x<t[mid])
hi=mid-1;
else if(x>t[mid])
lo=mid+1;
else
return t+mid;
}
return NULL;//把上述程序改成指针形式就会遇到麻烦,应为问题在于我们能否把gi初始化为t+n-1,应为当n=0是这是个无效的地址,所以必须对n=0的形式进行测试
}