随笔 - 7  文章 - 27  trackbacks - 0
<2010年10月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿

随笔档案(7)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

 1int 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 乔宁博 阅读(2001) 评论(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)
  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理