折半查找
來源：程序員人生 發布時間：2015-06-19 08:29:25 閱讀次數：2804次
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 版權所有.本站文章除注明出處外，皆為作者原創文章，可自由援用，但請注明來源.
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
