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

时间:2021-11-12 04:13:16
本文为原创,如需转载,请注明作者和出处,谢谢!

#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