折半查找
來源：程序員人生 發(fā)布時(shí)間：2015-06-19 08:29:25 閱讀次數(shù)：2812次
4.21號(hào)去參加阿里的實(shí)習(xí)生招聘，投遞的崗位是c/c++方向，下午2點(diǎn)，我悠閑的從學(xué)校北門前往悅豪酒店，走到酒店后掃描2維碼，去房間等待面試，面試的內(nèi)容觸及面非常廣。
從linux命令，STL ，操作系統(tǒng)，c/c++語法，算法，包羅萬象。下午迷迷糊糊面試完基本內(nèi)容后面試官給了我1張紙和筆讓我寫兩個(gè)算法，1：快速排序，2：折半查找。
固然快速排序我寫的還是很快的，可是當(dāng)我寫折半查找時(shí)悲劇產(chǎn)生了.
以下代碼是我在考場上所寫：
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);
}
當(dāng)我寫完后面試官問我，你覺得你寫的對嗎？我這個(gè)時(shí)候表現(xiàn)的非常機(jī)靈，我反問他你覺得對嗎？后來問了問stl的內(nèi)容，1面完后走出面試房間，我TM突然發(fā)現(xiàn)，沒有遞歸終止條件呀，如果查找不成功，low>=high時(shí)程序墮入死循環(huán).
改進(jìn)代碼：
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">點(diǎn)擊打開鏈接</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 ⑴;
}
問題總結(jié)：
1：寫遞歸函數(shù)時(shí)1定要有遞歸終止條件
2：面試時(shí)間可選擇時(shí)1定要選擇上午.
原文鏈接：http://www.52coder.net/archives/2472.html 版權(quán)所有.本站文章除注明出處外，皆為作者原創(chuàng)文章，可自由援用，但請注明來源.
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
