二分搜索是运用分治策略的典型例子
二分搜索方法充分利用了元素间的次序关系，采用分治策略，可在最坏情况下用O(logn)
的时间完成搜索任务。
看看下面的程序
////////////////////////////////////////
#include "iostream.h"
#include "iomanip.h"
#define max 100
template<class Type>
int BinarySearch( Type a[] , const Type &x , int n )
{
int left , right , mid;
left = 0;
right = n - 1;
while( left <= right )
{
mid = ( left + right ) / 2;
if( x == a[mid] )
return mid;
if( x < a[mid] )
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
void main()
{
int map[max] = { 1 , 2 , 4 , 5 , 7 , 8 };
int n = 6;
int x;
int i;
cout<<"数列:"<<endl;
for( i = 0 ; i < n ; i++ )
cout<<setw(5)<<map[i];
cout<<endl;
x = 3;
int order = BinarySearch( map , x , n );
if( order > 0 )
{
cout<<"指定数 "<<x<<" 处于第 "<<order+1<<" 位"<<endl;
}
else
{
cout<<"没有找到指定数 "<<x<<endl;
}
}
////////////////////////////////////////
其实在c语言库函数中已经有bsearch()了，
利用它可以更方便地解决二分查找问题。
#include "stdlib.h"
void* bsearch (
const void * key, //待查找单元的关键字
const void * base, //在什么地方找
size_t num, //有多少单元可以查找
size_t width, //每个单元占多少字节
int (*fncompare)(const void *, const void * ) //怎样比较两个元素大小
);
//程序举例
////////////////////////////////////////
#include "iostream.h"
#include "iomanip.h"
#include "stdlib.h" //注意这里
#define max 100
int cmp( const void *a , const void *b )
{
int x = *(int*)a;
int y = *(int*)b;
return x - y;
}
void main()
{
int map[max];
int n = 10;
int key;
int *item;
int i;
for( i = 0 ; i < n ; i++ )
{
map[i] = i * i + 3 * i + 4;
}
cout<<"数列:"<<endl;
for( i = 0 ; i < n ; i++ )
cout<<setw(5)<<map[i];
cout<<endl;
key = 44;
item = (int*)bsearch( &key , map , n , sizeof(int) , cmp );
if( item != NULL )
{
cout<<"指定数 "<<*item<<" 在数列中"<<endl;
}
else
{
cout<<"找不到指定数 "<<*item<<endl;
}
}
//
// 详细介绍可以到
// http://msdn.microsoft.com/library/default.asp?url=/library/en-us/vclib/html/_crt_bsearch.asp
////////////////////////////////////////
