编程珠玑 － 第四章习题

第四章讲的是二叉搜索，然后习题中要求实现二叉搜索，并要求在一个有序的数组中，查找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
 
  #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;}
 

我独立博客的 原文 欢迎大家访问