付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0

第四章讲的是二叉搜索,然后习题中要求实现二叉搜索,并要求在一个有序的数组中,查找key,并返回第一次出现的下标。

     最初的想法“先通过正常的二分查找返回一个位置pos,然后在二分查找0-pos,如果有合适的newpos继续0-newpos,不过是log2N + log2(N/2)+。。。”

    优化后

    1 正常的二分查找返回一个位置pos ,此时的pos  是由  left  right 生成 ,转到第二步

    2 继续调用 二分搜索 在 left 和 pos –1 中查找key , 如果找到 继续第二步,如果没有第三步

    3 此时可以说明 left – pos –1 中 不存在 key ,那么可以说 pos 就是第一次出现的下标

 

# include<stdio.h>
#define DEBUG 
int bsearch(int array[],int &start ,int &end ,int key)
{
    int i,j;
    int mid;
    i = start;
    j = end ;
    while(i <= j)
    {
        mid = (i+j)/2;
        #ifdef DEBUG
         //   printf("now i j and mid is %d %d %d\n",i,j,mid);
        #endif
        
        if(array[mid] == key)
            return mid;
        else if(array[mid] < key)
            i = mid + 1;
        else 
            j = mid - 1;
        
    }
    start = i,end = mid;
    return -1;
}
int FirstBsearch(int array[],int start ,int end ,int key)
{
    int i,j;
    int mid,pos;
    i = start;
    j = end ;
    mid = bsearch(array,start ,end ,key);
    if(array[mid] ==  key)//如果找到了
    {
        pos = mid;
        while( pos != -1 )
        {            
            j = pos -1;
            pos = bsearch(array ,i ,j ,key);
        }
        return j+1;
    } 
    return -1;
    
}
int main()
{
    int data[11] = {1,3,4,7,7,7,7,56,134,134,132487990};
    int key,i;
    int start = 0,end =10;
    for(i = 0 ; i < 4; i ++)
    {
        scanf("%d",&key);
        printf("%d",FirstBsearch(data,start,end,key));
    }
    return 0;
}

我独立博客的 原文   欢迎大家访问,批评指正;

http://www.fuxiang90.me/?p=85

posted on 2011-05-29 10:56 付翔 阅读(1739) 评论(0)  编辑 收藏 引用 所属分类: c++

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2011年5月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜