鱼C论坛

 找回密码
 立即注册
查看: 5927|回复: 20

[技术交流] Binary Search 半折法查找

[复制链接]
发表于 2011-4-28 23:24:46 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

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 有兴趣 大家一起讨论
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-5-1 08:37:09 | 显示全部楼层
不会啊,要何年何月才能学会啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-5-17 00:21:55 | 显示全部楼层
学习学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-5-17 00:32:44 | 显示全部楼层
学习学习学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2011-7-2 21:29:27 | 显示全部楼层
不会啊,要何年何月才能学会啊 :Q
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-5-17 13:44:36 | 显示全部楼层
无回帖,不论坛,这才是人道。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2013-5-24 15:07:50 | 显示全部楼层
激动人心,无法言表!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-5-25 17:22:58 | 显示全部楼层
感恩无私的分享与奉献 :)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-5-26 12:35:15 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-5-26 13:43:18 | 显示全部楼层
强烈支持楼主ing……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-4 20:40:45 | 显示全部楼层
谢谢楼主无私奉献
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-4 20:45:02 | 显示全部楼层
这个是二叉树的吧  是数据结构里的东西
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-5 18:05:03 | 显示全部楼层
谢谢楼主无私奉献
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-5 18:39:51 | 显示全部楼层
又称二分查找,不过得先对数组元素排序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-6 21:35:02 | 显示全部楼层
不错,考虑到了不浪费空间的问题,当输入几个数据时就分配几个数据的空间,还有一种折半查找的可以用递归的思想
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-7 19:01:39 | 显示全部楼层
谢谢分享 好好学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-8 15:03:24 | 显示全部楼层
无私奉献 向你学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-9 13:14:24 | 显示全部楼层
谢谢分享呀
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-10 15:56:37 | 显示全部楼层
积极回帖 好好学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2013-6-10 15:59:20 | 显示全部楼层
积极回帖向你学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-28 19:14

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表