随笔档案(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 乔宁博阅读(2055) 评论(6) 编辑收藏引用

FeedBack:

# re: 发一个二分查找的递归版本int B_search(int a[],int key,int size) 2010-10-12 10:30 陈梓瀚(vczh)

C++函数如果是尾递归是不能写成递归的……这个递归版本只有在haskell和类似语言上才有意义。回复更多评论

# re: 发一个二分查找的递归版本int B_search(int a[],int key,int size) 2010-10-12 10:48 schindlerlee

@陈梓瀚(vczh)
什么意思？为啥不能写成递归的？回复更多评论

# re: 发一个二分查找的递归版本int B_search(int a[],int key,int size) 2010-10-12 11:05 陈梓瀚(vczh)

@schindlerlee
因为写成递归的话，空间复杂度会从O(1)上升到O(lgn)，是不行的。回复更多评论

# re: 发一个二分查找的递归版本int B_search(int a[],int key,int size) 2010-10-12 11:13 schindlerlee

@陈梓瀚(vczh)
哦。。这个意思啊。。
回复更多评论

# re: 发一个二分查找的递归版本int B_search(int a[],int key,int size) 2010-10-12 16:17 陈梓瀚(vczh)

@schindlerlee
当然如果是haskell的话，他会发现然后帮你处理成非递归的，所以可以写…… 回复更多评论

# re: 发一个二分查找的递归版本int B_search(int a[],int key,int size) 2010-10-13 07:46 乔宁博(noble qiao)

对你说的那个haskell还不太了解，去学习学习@陈梓瀚(vczh)
回复更多评论

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！



网站导航: 博客园 IT新闻 BlogJava 知识库博问管理