Binary Search 半折法查找
本帖最后由 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 == find)
{
printf("The element you find locaed at %dth\n", (mid + 1));
exit(0);
}
if( local < find)
{
low = mid + 1;
}
if( local > 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 有兴趣 大家一起讨论 不会啊，要何年何月才能学会啊
学习学习学习 学习学习学习 不会啊，要何年何月才能学会啊 :Q 无回帖，不论坛，这才是人道。 激动人心，无法言表！ 感恩无私的分享与奉献 :) 强烈支持楼主ing…… 强烈支持楼主ing…… 谢谢楼主无私奉献 这个是二叉树的吧是数据结构里的东西 谢谢楼主无私奉献 又称二分查找，不过得先对数组元素排序 不错，考虑到了不浪费空间的问题，当输入几个数据时就分配几个数据的空间，还有一种折半查找的可以用递归的思想 谢谢分享 好好学习 无私奉献 向你学习 谢谢分享呀 积极回帖 好好学习 积极回帖向你学习
页:
[1]
2