折半查找
来源：程序员人生 发布时间：2015-06-19 08:29:25 阅读次数：2666次
4.21号去参加阿里的实习生招聘，投递的岗位是c/c++方向，下午2点，我悠闲的从学校北门前往悦豪酒店，走到酒店后扫描2维码，去房间等待面试，面试的内容触及面非常广。
从linux命令，STL ，操作系统，c/c++语法，算法，包罗万象。下午迷迷糊糊面试完基本内容后面试官给了我1张纸和笔让我写两个算法，1：快速排序，2：折半查找。
固然快速排序我写的还是很快的，可是当我写折半查找时悲剧产生了.
以下代码是我在考场上所写：
int binarysort(int a[],int low,int high,int x)
{
int mid=(low+high)/2;
if(a[mid]==x)
return mid;
else if(a[mid]<x)
binarysort(a,mid+1,high,x);
else
binarysort(a,low,mid⑴,x);
}
当我写完后面试官问我，你觉得你写的对吗？我这个时候表现的非常机灵，我反问他你觉得对吗？后来问了问stl的内容，1面完后走出面试房间，我TM突然发现，没有递归终止条件呀，如果查找不成功，low>=high时程序堕入死循环.
改进代码：
int binarysort(int a[],int low,int high,int x)
{
if(low>=high)
return ⑴;
else
{
int mid=(low+high)/2;
if(a[mid]==x)
return mid;
else if(a[mid]<x)
binarysort(a,mid+1,high,x);
else
binarysort(a,low,mid⑴,x);
}
}
更常见的折半查找情势：
int binarysort(int a[],int low,int high,int x)<a target=_blank href="http://www.52coder.net/archives/2472.html">点击打开链接</a>
{
if(low>=high)
return ⑴;
while(low<=high)
{
int mid=(low+high)/2;
if(a[mid]<x)
low=mid+1;
else if(a[mid]>x)
high=mid⑴;
else
return mid;
}
return ⑴;
}
问题总结：
1：写递归函数时1定要有递归终止条件
2：面试时间可选择时1定要选择上午.
原文链接：http://www.52coder.net/archives/2472.html 版权所有.本站文章除注明出处外，皆为作者原创文章，可自由援用，但请注明来源.
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
