隨筆檔案(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 喬寧博閱讀(2108) 評論(6) 編輯收藏引用

FeedBack:

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

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

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

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

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

@schindlerlee
因為寫成遞歸的話，空間復(fù)雜度會從O(1)上升到O(lgn)，是不行的。回復(fù) 更多評論

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

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

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

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

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

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

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



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