|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 LNH_Sniper 于 2011-4-29 17:47 编辑
关于半折法查找，是减少搜索范围，同时缩短搜索时间。因为与遍历相比 Binary Search的时间复杂度为O(log(n))
Binary Search 的局限：只能在 有序 序列中进行查找。
下面说下原理：
有如下10个元素 首先需要定义: length --长度
mid----中间位
low-------低位
high------高位
find-------带查找值
eg. 1 2 3 4 5 6 7 8 9 10
low = 0 mid = (low + high) / 2 high = length - 1
这个例子中 计算出 mid = 5 high = 9
我们用 find 的值和中间值进行比较 有三种情况：第一、与中间值相等 那么 输出
第二、比中间值小 那么意味着查找结果只能在前半段 所以我们对范围
进行修改 low = 0
high = mid - 1
mid = (low + high ) / 2 新的中间点
第三、比中间值大 那么意味着查找结果只能在后半段 所以我们对范围
进行修改 low = mid + 1
high = length -1
mid = (low + high) / 2新的中间点
循环结束的标志 是 low <= high
如果循环结束后 没有相应的结果 那么 输出 查找元素不存在
完整程序 如下：
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
int *init_array(int n)
{
return (int *)malloc(sizeof(int) * n);
}
void binary_search(int *local,int find,int length)
{
int low, high, mid;
low = 0;
high = length;
while(low <= high)
{
mid = (low + high) / 2;
if( local[mid] == find)
{
printf("The element you find locaed at %dth\n", (mid + 1));
exit(0);
}
if( local[mid] < find)
{
low = mid + 1;
}
if( local[mid] > find)
{
high = mid -1;
}
}
printf("No Such Elemment Finded!!\n");
}
int main()
{
int find,len, *local, *temp, length;
printf("Put The length of integer:");
scanf("%d",&len);
length = len;
temp = local = init_array(len);
printf("The elemments of thie array:");
while( len-- )
{
scanf("%d",temp++);
}
printf("The Elemment You Want Find:");
scanf("%d",&find);
binary_search(local, find, length);
return 0;
}
程序没有写 注释 在VC6.0 条件下通过 每步执行有相应提示。
希望大家对算法多交流 我比较喜欢ACM 有兴趣 大家一起讨论 |
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2011-4-28 23:24:46
置顶卡
千斤顶
显身卡
发表于 2011-5-1 08:37:09