常見幾種二分查找

二分查找經典的算法很簡單，基本注意下循環終止條件和計算中間值mid坐标時注意一下溢出問題，就可以了。下面給出根據二分查找變形求一些特殊值的算法。有問題煩請指正

// 經典二分查找

int binary_search( int a[], int n, int value )

{

if( n == 0 )return -1;

int low = 0, high = n - 1;

while( low <= high )

{

int mid = low + ( ( high - low ) >> 1 ) ;

if( a[ mid ] == value )return mid;

else if( a[ mid ] > value )high = mid - 1;

else

{

low = mid + 1;

}

}

return -1;

}

// 查找等于value的第一個元素

int binary_search_first( int a[], int n, int value )

{

if( n == 0 )return -1;

int low = 0, high = n - 1;

while( low < high - 1 )

{

int mid = low + ( ( high - low ) >> 1 ) ;

if( a[ mid ] >= value )high = mid;

else

{

low = mid + 1;

}

}

if ( a[ low ] == value )return low;

else if ( a[ high ] == value )return high;

return -1;

}

// 查找等于value最後一個元素

int binary_search_last( int a[], int n, int value )

{

if( n == 0 )return -1;

int low = 0, high = n - 1;

while( low < high - 1 )

{

int mid = low + ( ( high - low ) >> 1 ) ;

if( a[ mid ] <= value )low = mid;

else

{

high = mid - 1;

}

}

if ( a[ high ] == value )return high;

else if ( a[ low ] == value )return low;

return -1;

}

// 查找小于value的最大值

int low_bound( int a[], int n, int value )

{

if( n == 0 )return -1;

int low = 0, high = n - 1;

while( low <= high )

{

int mid = low + ( ( high - low ) >> 1 );

if( a[ mid ] >= value )high = mid - 1;

else

{

low = mid + 1;

}

}

if( low > 0 )return low - 1;

return -1;

}

// 查找大于value的最小值

int up_bound( int a[], int n, int value )

{

if( n == 0 )return -1;

int low = 0, high = n - 1;

while( low <= high )

{

int mid = low + ( ( high - low ) >> 1 );

if( a[ mid ] <= value )low = mid+1;

else

{

high = mid - 1;

}

}

if( high < n - 1 )return high + 1;

return -1;

}