黑马程序员技术交流社区
标题:
请教折半查找的问题，谢谢！
[打印本页]
作者:
党巾水
时间:
2012-4-3 21:35
标题:
请教折半查找的问题，谢谢！
在自学视频的时候，学到第4天第7个视频（折半查找），讲折半查找的一个应用是在一个给定的有序数组中插入一个元素后仍保持数组的有序。
毕老师的方法是把最后的
return
-1;
改成
return min;
。我尝试后发现确实可以，但是不明白为什么不能改成
return max;
（改成max后是错误的）。
我思考如下：插入一个数字，去和arr[mid]比较，可能大去做min=mid+1; 可能小去做 max=mid-1;
这两个可能都存在，但是最后如果返回 min 作为插入数字的位置就对，如返回 max 作为插入数字的位置就错。就不明白了~~
哪位解答下？谢谢！
public static int halfsearch(int[] arr,int key)
{
int min=0,max=arr.length-1,mid;
while(min<=max)
{
mid=(min+max)/2;
if(key>arr[mid])
min=mid+1;
else if(key<arr[mid])
max=mid-1;
else
return mid;
}
return
-1;
return min;
return max;
}
作者:
郑苑东
时间:
2012-4-3 22:24
因为当你的值小于max索引的值时，max就会减一，这是max下标索引的值就是比key大的那个数的前一个。这时候插入，就等于在会出错。。。例如key = 100；new int[]{1, 2, 3, 30,190}，key 小于190，可是这是因为进入了if(key<arr[mid]) max=mid-1; mid这时候等于min等于max，（这时候本来是要插入在190的位置）可是max再减一就会把插入位置提前一个位置。变成在30前面。所以会出错。。。
作者:
郑苑东
时间:
2012-4-3 22:25
我没看毕老师的。。从你代码推算出来的你的意思。也不知道你是不是问这个。。。
作者:
尹博
时间:
2012-4-3 22:40
很简单，因为若查找的数不在数组中，那while循环必然要经历min==max这个临界条件，此时若要查找的数key>arr[mid]，则min+1，小于则max-1，这两种情况都使得key的大小在下标为max和min的元素之间，将key插入数组中则使key之后所有的元素的角标都增加1（若key之后有元素的话），若返回的是max，则key占用max这个角标，max所在角标的元素将后移，此时key就不再在max和min之间了（max、min所在的元素都后移）。
作者:
党巾水
时间:
2012-4-3 22:49
明白，谢谢二位！
作者:
吴玉辉
时间:
2012-4-3 22:50
做一个实例有序数组，取长一点，插入的数值偏小一些，然后按照循环你在纸上标记出指针min，mid，max。按照循环中代码，你会发现当循环判断条件不成立时，max指针已经左移出了数组，而数组中的角标是大于等于0的整数，所以会报异常
作者:
niceBoy
时间:
2012-4-3 22:54
例：int[] arr = {1,3,6};key=2;
代入:
第一次while(0<=2)成立，mid=1满足key<int[1]，则max=0
第二次whiel(0<=0)成立，mid=0满足kye>int[0]，则min=1
第三次while(1<=0)不成立结束
此时max=0,min=1
而插入的实际位置是1，也就是min，
结论：看不懂建议在纸上写下程序运行过程会清楚些，毕竟光看代码眼花头疼（大虾就算了）
作者:
党巾水
时间:
2012-4-3 23:45
本帖最后由 刘馨琪 于 2012-4-3 23:47 编辑
我在纸上做过，也知道最后是min对，只是不明白为什么是min对。而且数组元素少得出的结论未必能说明元素多的数组。无法确定从个别数组归纳出来的一定可以广泛应用。但是刚才看了几位的分析后发现其实新的key位置应该在【min，max+1】闭区间（就是【0，arr.length】闭区间），这也辅助说明了楼上几位的说法。所以明白了。谢谢！
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2