隨筆檔案(7)

int B_search(int a[],int key,int size)
2

{
3

if(size<0)
4

return -1;
5

int mid=size/2;
6

if(a[mid]==key)
7

return mid;
8

else if(a[mid]>key)
9

return B_search(a,key,mid-1);
10

else if(a[mid]<key)
11

return B_search(a+mid+1,key,size-(mid+1))+mid+1;
12

}

posted on 2010-10-11 23:52 喬寧博閱讀(2107) 評(píng)論(6) 編輯收藏引用

FeedBack:

# re: 發(fā)一個(gè)二分查找的遞歸版本int B_search(int a[],int key,int size) 2010-10-12 10:30 陳梓瀚(vczh)

C++函數(shù)如果是尾遞歸是不能寫(xiě)成遞歸的……這個(gè)遞歸版本只有在haskell和類似語(yǔ)言上才有意義。回復(fù) 更多評(píng)論

# re: 發(fā)一個(gè)二分查找的遞歸版本int B_search(int a[],int key,int size) 2010-10-12 10:48 schindlerlee

@陳梓瀚(vczh)
什么意思？為啥不能寫(xiě)成遞歸的？回復(fù) 更多評(píng)論

# re: 發(fā)一個(gè)二分查找的遞歸版本int B_search(int a[],int key,int size) 2010-10-12 11:05 陳梓瀚(vczh)

@schindlerlee
因?yàn)閷?xiě)成遞歸的話，空間復(fù)雜度會(huì)從O(1)上升到O(lgn)，是不行的。回復(fù) 更多評(píng)論

# re: 發(fā)一個(gè)二分查找的遞歸版本int B_search(int a[],int key,int size) 2010-10-12 11:13 schindlerlee

@陳梓瀚(vczh)
哦。。這個(gè)意思啊。。
回復(fù) 更多評(píng)論

# re: 發(fā)一個(gè)二分查找的遞歸版本int B_search(int a[],int key,int size) 2010-10-12 16:17 陳梓瀚(vczh)

@schindlerlee
當(dāng)然如果是haskell的話，他會(huì)發(fā)現(xiàn)然后幫你處理成非遞歸的，所以可以寫(xiě)…… 回復(fù) 更多評(píng)論

# re: 發(fā)一個(gè)二分查找的遞歸版本int B_search(int a[],int key,int size) 2010-10-13 07:46 喬寧博(noble qiao)

對(duì)你說(shuō)的那個(gè)haskell還不太了解，去學(xué)習(xí)學(xué)習(xí)@陳梓瀚(vczh)
回復(fù) 更多評(píng)論

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！



網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理