黑马程序员技术交流社区

标题: Collections.binarySearch的问题 [打印本页]

作者: 程序猿 时间: 2012-4-30 21:20
标题: Collections.binarySearch的问题
这是老师讲折半查找的模拟binarySearch的一个函数，
public static int halfSearch(List<String> list,String key)
{
int max,min,mid;
max=list.size()-1;
min=0;
while(min<=max)
{
mid=(max+min)>>1;
String str=list.get(mid);
int num=str.compareTo(key);
if(num>0)
max=mid-1;
else if(num<0)
min=min+1;
else
return mid;

}
return -min-1;
}
最后的return -min-1;说是返回的插入点减1;可写得程序明显不是负的插入点减1嘛？
还有就是最后的min值为什么是插入点，我没反应过来。

作者: 何阳 时间: 2012-4-30 22:16
//例如一个数组[1,3,5,7,9]
//你要查找4插入的位置你该怎么做，第一次在数组中查找，发现应该做在0和2的位置里面
//这个是时候min是0，max是2，mid是1，第二次比较，发现在1和2之间
//再次折中min是1，max是2，mid是（1+2）/2=1，发现在比3大，
//再次折中，min是2，max是2，mid是（2+2）/2=2,发现比5小
//再次折中，min是2，max是1，while条件不成立，
//以此分析，你觉的你要插入的数放在那个地方，肯定是最后一次循环条件不成立是min的位置上，就是2的位置上
//因为比较的那个数比min大，所以再次折中，发现条件不成立才停止循环。
//如果你插入的是0，依次类推，折中，再次折中，发现0比中间值1还小。再次循环，条件不成立
//所以应该将数字插入min的位置上，就是2的位置上，因为0代表数组的第一个元素，所以将减min-1；

作者: 程序猿 时间: 2012-4-30 22:42

天道酬勤发表于 2012-4-30 22:16
//例如一个数组[1,3,5,7,9]
//你要查找4插入的位置你该怎么做，第一次在数组中查找，发现应该做在0和2的位 ...

第一次是max=4，min=0，mid=2；比较后，max=mid-1=1；min=0；mid=0；再比较后 min=mid+1=1，max=1；mid=1；再比较，min=mid+1=2；max=1；循环退出。min=2；有点懂了。但为什么是return -min-1啊

作者: 何阳 时间: 2012-4-30 22:56
//如果你要查找的在这个数组的最左边，返回的应该是个0-1=-1；但是右边呢？就是4-1=3；
//这样不是说明了在数组中存在吗？所以用-min表示这个数在数组不存在,-min-1=-4-1=-5;
//这样我们就知道了要查找的数应该插入4的后面，这样加以区分的.o了。

作者: 陈苓 时间: 2012-4-30 23:06
折半查找首先要保证元素有序的，给我一个数如果在数组中查找不到，因为min是数组的0角标，那就min-1返回的就是-1，表示这个数没有在我这个数组中，找不到这个数返回值可以自己定义，你不用min-1，直接返回-1，也行，也可以代表这个数没有在此数组中。还有可以抛出一个RuntimeException异常。

作者: 程序猿 时间: 2012-4-30 23:23

天道酬勤发表于 2012-4-30 22:56
//如果你要查找的在这个数组的最左边，返回的应该是个0-1=-1；但是右边呢？就是4-1=3；
//这样不是说明了在 ...

明白了，为了在插入点在最左边时不返回0，所以需要-1，对吧
谢谢你哦~

作者: 何阳 时间: 2012-5-1 00:17
嗯，怎么没技术分啊，郁闷.......

作者: 程序猿 时间: 2012-5-1 00:48

天道酬勤发表于 2012-5-1 00:17
嗯，怎么没技术分啊，郁闷.......

老师没上线呢吧，你不是实名，好像没技术分的。会给你论坛金钱~

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

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