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

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

 #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[] = {1, 4, 5, 7, 9};     
    printf("%d \n", binary_search_recursion(9, data, 0, 4));     
    printf("%d \n", binary_search(9, data, 0, 4));     
    printf("%d \n", binary_search_recursion(90, data, 0, 4));     
    printf("%d \n", binary_search(89, data, 0, 4));     
    return 0; 
} 

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

评论

# re: 拆半查找的递归和非递归算法 2008-05-12 10:26 apPZ

2分法不是这样写的吧?  回复  更多评论   

# re: 拆半查找的递归和非递归算法 2008-05-12 15:56 dreamingnest

嗯，应该是的，只是测试的例子多了些，也看了好半天。汗``  回复  更多评论   

# re: 拆半查找的递归和非递归算法 2008-05-12 19:49 www

i = (b + e) / 2; 有问题，会溢出的。sun的jdk里面的二分查找源码原先也有同样的问题。
  回复  更多评论   

# re: 拆半查找的递归和非递归算法 2008-05-12 21:48 银河使者

没错 i = (b + e) / 2; 这句有隐患，当b+e大于int范围时就会溢出。解决的方法是i = b/2 + e/2。这样用2先除一下，就不会溢出了。  回复  更多评论   


标题  
姓名  
主页
验证码 *  
内容(请不要发表任何与政治相关的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
该文被作者在 2008-05-24 08:58 编辑过
 
成果网帮您增加网站收入
 
相关链接:
网站导航:




<2008年5月>
日一二三四五六
27282930123
45678910
11121314151617
18192021222324
25262728293031
1234567

导航

统计

公告

我的其他blog
http://nokiaguy.cnblogs.com

常用链接

留言簿(4)

我参与的团队

随笔分类(145)

随笔档案(66)

相册

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

60天内阅读排行