牵着老婆满街逛

严以律己,宽以待人. 三思而后行.
GMail/GTalk: yanglinbo#google.com;
MSN/Email: tx7do#yahoo.com.cn;
QQ: 3 0 3 3 9 6 9 2 0 .

折半查找(二分查找)

最基本的算法:
int BinarySearch(int arr[], int len, int searchKey)
{
    
int start = 0, end = len - 1, mid;
    
while (start <= end)
    
{
        
// 求中间的索引值
        mid = (start + end) / 2;

        
if (arr[mid] == number)
        
{
            
// 查到了
            return mid;
        }

        
else if (arr[mid] < searchKey)
        
{
            
// 搜索范围缩小到后半部
            start = mid + 1;
        }

        
else if (arr[mid] > searchKey)
        
{
            
// 搜索范围缩小到前半部
            end = mid - 1;
        }

    }


    
// 没查到
    return -1;
}


用到递归的算法:
int BinarySearch( const int arr[], int searchKey, int start, int end )
{
    
// 求中间的索引值
    int mid = ( start + end ) / 2;

    
if ( searchKey == arr[ mid ] )
    
{
        
// 找到了
        return mid;
    }

    
else if ( searchKey < arr[ mid ] )
    
{
        
// 搜索范围缩小到前半部
        return BinarySearch( arr, searchKey, start, mid - 1 );
    }

    
else if ( searchKey > arr[ mid ] )
    
{
        
// 搜索范围缩小到后半部
        return BinarySearch( arr, searchKey, mid + 1, end );
    }

    
else
    
{
        
// 没有查找到
        return -1;
    }

}


使用迭代实现:
int BinarySearch( const int arr[], const int& len, const int& searchKey )
{  
    
int start=0, end=len-1, mid;
    
while ( start < end )
    
{
        mid 
= (start + end) / 2;

        
if ( searchKey > arr[mid] )
        
{
            start 
= mid + 1;
        }

        
else
        
{
            end 
= mid;
        }

    }


    
if ( start > end )
    
{
        
return -1;
    }

    
else
    
{
        
if ( searchKey == arr[start] )
        
{
            
return start;
        }

        
else
        
{
            
return -1;
        }

    }

}



测试代码:
void testBinarySearch()
{
    
const int LEN = 8;
    
int a[LEN] = 12225689 };

    printf(
"查找到的索引号为:%d\n", BinarySearch(a, LEN, 5));

    printf(
"查找到的索引号为:%d\n", BinarySearch(a, 50, LEN-1));
}

posted on 2010-06-02 23:21 杨粼波 阅读(587) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理