黑马程序员技术交流社区

标题: 折半查找的理论不是很理解 [打印本页]

作者: 云水禅心 时间: 2013-9-22 22:20
标题: 折半查找的理论不是很理解
本帖最后由杨增坤于 2013-9-23 16:57 编辑

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

作者: 刘亮 时间: 2013-9-22 22:26
★折半查找：
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;
}

作者: 云水禅心 时间: 2013-9-22 22:33
min =mid+1; max = mid-1; 这两句我不理解多谢

作者: xscn 时间: 2013-9-22 22:37
折半查找适用有序数列，实际上是一种跳跃方式的查找，每经过一次比较,查找范围就缩小一半，减少比较次数，比较高效。
思路就是：
1.先确定有序数列的中间位置
2.用待查值与中间位置的值进行比较
3.要是大于中间值，在后半个区域继续进行折半查找
要是小于中间值，在前半个区域继续进行折半查找

作者: xscn 时间: 2013-9-22 22:44

云水禅心发表于 2013-9-22 22:33
min =mid+1; max = mid-1; 这两句我不理解多谢

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

作者: 云水禅心 时间: 2013-9-22 22:54
好的谢谢我会用这样的方法试试看的

作者: yting_xmei1129 时间: 2013-9-22 23:58
折半查找法其基本思想是：设查找数据的范围下限为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，说明没有此数，打印找不到信息，程序结束。

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

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

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

作者: 朱艳 时间: 2013-9-23 07:50
这般查找的数组都是有序的，每次比对的元素也只有 mid指向的元素， mid由max和min决定，当key>arr[mid]时说明mid取小了，要改变min界标，故min =mid+1，另一句也是同样的原理。

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

作者: 曾林魁 时间: 2013-9-23 14:51
你好，首先，折半查找的前提是要你要查找的数组必须有序，对于折半查找，充分利用了元素间的次序关系，采用分治策略，可在最坏的情况下用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，即查找不到最后一个或第一个值。可以在比较到最后两个数时，再次判断到底是哪个值和查找的值相等。

作者: ｊìｎｇ╮煜 时间: 2013-9-23 15:04
折半就是比大小了. 首先一排有序数组........
然后输入你要查找的key. 然后拿key和最数组最中间的那个数相比较,由于此数组是有序的,所以如果这个key比中间的那个数大,那么key的位置肯定在右边.如果小,肯定在左边.
然后再从右边,或者左边找到它们的一半的位置.

作者: 云水禅心 时间: 2013-9-23 20:29
谢谢各位同仁，我明白了

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2