随笔 - 312, 文章 - 14, 评论 - 1393, 引用 - 0
数据加载中……

拆半查找的递归和非递归算法

本文为原创,如需转载,请注明作者和出处,谢谢!

#include <stdio.h>  

int binary_search(int x, int data[], int b, int e) 
{     
    
int i;     
    
while(b <= e)     
    {     
        i 
= (b + e) / 2;     
        
if(data[i] == x) return i;     
        
if(data[i] < x)          
            b 
= i + 1;     
        
else         
            e 
= i - 1;             
    }     
    
return -1;     
}  

int binary_search_recursion(int x, int data[], int b, int e) 
{     
    
int i;     
    i 
= (b + e) / 2;     
    
if(b > e) return -1;     
    
if(data[i] != x)     
    {     
        
if(x < data[i])         
            
return binary_search_recursion(x, data, 0, i - 1);     
        
else         
            
return binary_search_recursion(x, data, i + 1, e);     
    }     
    
else         
        
return i; 
}  

int main() 
{     
    
int data[] = {14579};     
    printf(
"%d \n", binary_search_recursion(9, data, 04));     
    printf(
"%d \n", binary_search(9, data, 04));     
    printf(
"%d \n", binary_search_recursion(90, data, 04));     
    printf(
"%d \n", binary_search(89, data, 04));     
    
return 0




Android开发完全讲义(第2版)(本书版权已输出到台湾)

http://product.dangdang.com/product.aspx?product_id=22741502



Android高薪之路:Android程序员面试宝典 http://book.360buy.com/10970314.html


新浪微博:http://t.sina.com.cn/androidguy   昵称:李宁_Lining

posted on 2008-05-11 22:26 银河使者 阅读(2703) 评论(4)  编辑  收藏 所属分类: algorithmC/C++ 原创

评论

# re: 拆半查找的递归和非递归算法  回复  更多评论   

2分法不是这样写的吧?
2008-05-12 10:26 | apPZ

# re: 拆半查找的递归和非递归算法  回复  更多评论   

嗯,应该是的,只是测试的例子多了些,也看了好半天。汗``
2008-05-12 15:56 | dreamingnest

# re: 拆半查找的递归和非递归算法  回复  更多评论   

i = (b + e) / 2; 有问题,会溢出的。sun的jdk里面的二分查找源码原先也有同样的问题。
2008-05-12 19:49 | www

# re: 拆半查找的递归和非递归算法  回复  更多评论   

没错 i = (b + e) / 2; 这句有隐患,当b+e大于int范围时就会溢出。解决的方法是i = b/2 + e/2。这样用2先除一下,就不会溢出了。
2008-05-12 21:48 | 银河使者

只有注册用户登录后才能发表评论。


网站导航: