分治与递归策略_二分搜索法

王朝other·作者佚名  2006-01-10
窄屏简体版  字體: |||超大  

二分搜索是运用分治策略的典型例子

二分搜索方法充分利用了元素间的次序关系,采用分治策略,可在最坏情况下用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

////////////////////////////////////////

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航