A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 云水禅心 中级黑马   /  2013-9-22 22:20  /  2560 人查看  /  11 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 杨增坤 于 2013-9-23 16:57 编辑

今天看了折半查找的视频,但是不是很理解,请教各位高手,能不能用你们对这知识的理解思路向我讲解。多谢多谢。

评分

参与人数 1技术分 +1 收起 理由
黄兴旺 + 1

查看全部评分

11 个回复

倒序浏览
★折半查找:
public static void main(String[] args)   //这是毕老师视频讲解的例子 给你分析下
        {
                int[] arr={3,5,7,9,12,21};
                int z=zheban(arr,7);
                System.out.println(z);
        }
        public static int zheban(int[] arr,int key)
        {
                int max,min,mid; //三个变量,中等 低等 高等
                min=0; //数组都是0角标 比较
                max=arr.length-1; //相邻比较,少一
                mid=(min+max)/2; //折半。 就是取中间 如果偏大 就往右 小就左
                while (arr[mid]!=key) //。。看毕老师视频 多看变
                {
                        if (key>arr[mid])
                        {
                                min =mid+1;
                        }
                        else if (key<arr[mid])
                        {
                                max = mid-1;
                        }
                        mid =(max+min)/2;
                }
                return mid;
        }

评分

参与人数 1技术分 +1 收起 理由
黄兴旺 + 1

查看全部评分

回复 使用道具 举报
min =mid+1;    max = mid-1;   这两句我不理解     多谢
回复 使用道具 举报
折半查找适用有序数列,实际上是一种跳跃方式的查找,每经过一次比较,查找范围就缩小一半,减少比较次数,比较高效。
思路就是:
1.先确定有序数列的中间位置
2.用待查值与中间位置的值进行比较
3.要是大于中间值,在后半个区域继续进行折半查找
要是小于中间值,在前半个区域继续进行折半查找

                 

评分

参与人数 1技术分 +1 收起 理由
黄兴旺 + 1

查看全部评分

回复 使用道具 举报
云水禅心 发表于 2013-9-22 22:33
min =mid+1;    max = mid-1;   这两句我不理解     多谢

就是指针移位 重新确定折半的范围是前半还是后半 你想象一下折筷子

回复 使用道具 举报
好的  谢谢   我会用这样的方法试试看的
回复 使用道具 举报
折半查找法其基本思想是: 设查找数据的范围下限为l=1,上限为h=5,求中点m=(l+h)/2,用X与中点元素am比较,若X等于am,即找到,停止查找;否则,若X大于am,替换下限l=m+1,到下半段继续查找;若X小于am,换上限h=m-1,到上半段继续查找;如此重复前面的过程直到找到或者l>h为止。如果l>h,说明没有此数,打印找不到信息,程序结束。

不知道这样楼主明白了没有,希望可以帮到楼主、、、

评分

参与人数 1技术分 +1 收起 理由
黄兴旺 + 1

查看全部评分

回复 使用道具 举报
肖勇 中级黑马 2013-9-23 00:02:08
8#
举个最明显的例子,假如要在1,2,3,4,5,6,7中查找6的位子(要保证集合中的对象是有序的),我们肯定是     先用key值去找中间的中间的数,先找到4,6比4大,所以肯定在4的右边,原来的index是在0角标位子,所以index就变成了数字5所对应的角标4,然后在数字4的右边的这些数字(5,6,7)中有按照刚刚的方法,先找中间的数,此时中间的数变成了6,此时找到了key值,返回所对应的角标。

不知道这样说你能不能懂? 如果你想多了解一下这些查找的方法,建议可以去看一下数据结构。

评分

参与人数 1技术分 +1 收起 理由
黄兴旺 + 1

查看全部评分

回复 使用道具 举报
朱艳 中级黑马 2013-9-23 07:50:22
9#
这般查找的数组都是有序的 ,每次比对的元素也只有 mid指向的元素, mid由max和min决定,当key>arr[mid]时 说明mid取小了,要改变min界标,故min =mid+1,另一句也是同样的原理。

新建位图图像.jpg (23.96 KB, 下载次数: 56)

新建位图图像.jpg

评分

参与人数 1技术分 +1 收起 理由
杨增坤 + 1

查看全部评分

回复 使用道具 举报
你好,首先,折半查找的前提是要你要查找的数组必须有序,对于折半查找,充分利用了元素间的次序关系,采用分治策略,可在最坏的情况下用O(log n)完成搜索任务。
它的基本思想是,将n个元素分成个数大致相同的两半,取a[n/2]与欲查找的x作比较,如果x=a[n/2]则找到x,算法终止。如 果x<a[n/2],则我们只要在数组a的左半部继续搜索x(这里假设数组元素呈升序排列)。如果x>a[n/2],则我们只要在数组a的右 半部继续搜索x。
不过折半查找法一般都存在一个临界值的BUG,即查找不到最后一个或第一个值。可以在比较到最后两个数时,再次判断到底是哪个值和查找的值相等。

评分

参与人数 1技术分 +1 收起 理由
杨增坤 + 1

查看全部评分

回复 使用道具 举报
折半就是比大小了.  首先一排有序数组........
然后输入你要查找的key.   然后拿key和最数组最中间的那个数相比较,由于此数组是有序的,所以如果这个key比中间的那个数大,那么key的位置肯定在右边.如果小,肯定在左边.
然后再从右边,或者左边找到它们的一半的位置.

评分

参与人数 1技术分 +1 收起 理由
杨增坤 + 1

查看全部评分

回复 使用道具 举报
  谢谢 各位同仁,我明白了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马