第四章講的是二叉搜索，然后習(xí)題中要求實(shí)現(xiàn)二叉搜索，并要求在一個有序的數(shù)組中，查找key，并返回第一次出現(xiàn)的下標(biāo)。

     最初的想法“先通過正常的二分查找返回一個位置pos，然后在二分查找0-pos，如果有合適的newpos繼續(xù)0-newpos，不過是log2N + log2(N/2)+。。。”

    優(yōu)化后

    1 正常的二分查找返回一個位置pos ，此時的pos  是由  left  right 生成 ，轉(zhuǎn)到第二步

    2 繼續(xù)調(diào)用 二分搜索 在 left 和 pos –1 中查找key ， 如果找到 繼續(xù)第二步，如果沒有第三步

    3 此時可以說明 left – pos –1 中 不存在 key ，那么可以說 pos 就是第一次出現(xiàn)的下標(biāo)

# 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;
}

我獨(dú)立博客的　原文　　　歡迎大家訪問，批評指正；

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