黑马程序员技术交流社区

标题: 关于数组的折半查找提问 [打印本页]

作者: air 时间: 2013-10-17 13:59
标题: 关于数组的折半查找提问
视频里老师讲的我一知半解.似懂不懂,我该怎么理解那个中间的mid加一或者减一呢?绕的我晕晕的
我想知道详细一点关于折半查找的实现方式?

作者: 赖波 时间: 2013-10-17 14:20
点这个里面写得很好：
http://bbs.itheima.com/forum.php ... ;pre_pos=5&ext=

作者: 風諾 时间: 2013-10-17 14:24
本帖最后由風諾于 2013-10-17 14:28 编辑

首先要明确数组是有序的，元素按照大小依次排好的
这样取中间值去和要查找的数作比较
比中间值大就往上找，比中间值小就往下找

public static int halfsearch(int[] arr,int key) {
int min = 0,max = arr.length - 1,mid = (min + max)/2; //初始值的设定
while(arr[mid] != key) {
if(key < arr[mid]) //key值处在min和mid之间
max = mid - 1; //那么key已经小于了arr[mid],只要在min~(mid-1)之间查找，因此新的max的值就是mid-1
if(key > arr[mid]) //key值处在mid和max之间
min = mid + 1; //那么key已经大于了arr[mid],只要在(mid+1)~max之间查找，因此新的min的值就是mid+1
mid = (max + min)/2; //有了新的范围以后，就设定处在新范围中间的值为mid这样每次比较都缩小一半的范围
}
return mid;
}

复制代码

若是数组中根本没有这个值，需要另作处理

作者: ...... 时间: 2013-10-17 14:24
首先，你要明确折半查找是对排好序的数组才适用，这是前提。
然后，定义的三个变量，max(最大的数的下标，也就是数组的最后一个数），min(最小的数的下标，也就是第一个数）一般 max= arr.length(数组的长度）min = 0;然后mid=（max+min)/2 那么arr[mid]就表示数组正中间的数，
接着，用传进来的数和arr[mid]比较
1、如果num>arr[mid]，则你要找的数的位置肯定实在数组的后半部分（因为数组是已经排好序的），这时，你需要做的就是让num和数组的后半部分比较，也为你每一次比较都是让num和arr[mid]比较，所以，你要改变mid的值，又因为mid和max，min有关，这时你就需要让min改变，min= mid +1;这时，arr[min]指的就是数组中间的后一个数，而arr[mid]就成了arr数组后半部分的中间部分，这时，num再与arr[mid]比较....一次类推
2、如果1中的比较结果num<arr[mid]这说明你要找的说在数组的前半部分，你就要让mid往前移动，也就是max= mid-1;然后mid=(max+min)/2，mid就变小了，然后再比较，以此类推...

作者: air 时间: 2013-10-17 15:15
几位说的非常好,我明白了.非常感谢

作者: 李文帅 时间: 2013-10-17 16:25
这是我自己的理解，跟楼上的差不多，希望对你有所帮助
首先数组必须是有序数组，每次用中间值与要查找的元素进行比较，如果比中间值大则在中间值~最大值之间找，否则在最小值~中间值之间找
F:\TDDownload\halfsearch.PNG

作者: 李文帅 时间: 2013-10-17 16:34
不好意思，我是新手，本来想添加图片的，好像是权限不够吧，只能添加附件了...

falfsearch.PNG (35.95 KB, 下载次数: 8)

作者: 李江 时间: 2013-10-18 19:50

楼主你好，如果问题已解决请将帖子状态修改为提问结束，如果未解决请继续提问，谢谢合作
如果不会修改请看解释帖：http://bbs.itheima.com/thread-89313-1-1.html

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

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