黑马程序员技术交流社区
标题:
关于集合框架工具类 Collections 的疑问!!!
[打印本页]
作者:
尖卡斌引
时间:
2013-5-17 15:39
标题:
关于集合框架工具类 Collections 的疑问!!!
在Collections 中 使用二分法查找相应的元素使用的是
Collections.binarySearch( , "元素");
返回的应该是该元素的角标,我们常理解的角标是从 0 开始 递增的。
为什么在这里返回的角标要是负的呢???,这样做的目的是什么???有什么好处??
请详细解释下。谢谢!!
作者:
刘学明
时间:
2013-5-17 15:47
哪里是负的?
作者:
萌小子
时间:
2013-5-17 16:00
如果元素存在就返回元素的索引,如果不存在就返回 - 1。
下面是API中的
binarySearch
public static <T> int binarySearch(List<? extends Comparable<? super T>> list,
T key)使用二分搜索法搜索指定列表,以获得指定对象。在进行此调用之前,必须根据列表元素的自然顺序对列表进行升序排序(通过 sort(List) 方法)。如果没有对列表进行排序,则结果是不确定的。如果列表包含多个等于指定对象的元素,则无法保证找到的是哪一个。
此方法对“随机访问”列表运行 log(n) 次(它提供接近固定时间的位置访问)。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表,则此方法将执行基于迭代器的二分搜索,执行 O(n) 次链接遍历和 O(log n) 次元素比较。
参数:
list - 要搜索的列表。
key - 要搜索的键。
返回:
如果搜索键包含在列表中,则返回搜索键的索引;否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点:即第一个大于此键的元素索引;如果列表中的所有元素都小于指定的键,则为 list.size()。注意,这保证了当且仅当此键被找到时,返回的值将 >= 0。
抛出:
ClassCastException - 如果列表中包含不可相互比较 的元素(例如,字符串和整数),或者搜索键无法与列表的元素进行相互比较。
作者:
Super_Class
时间:
2013-5-17 16:22
|——二分查找(前提是数组是有序的)
用三个指针来操作十足数组。(我的理解是,一打两断,只要一半。)
if(key>arr[mid])
min = mid +1; //要找的元素大于中间的元素,我就要mid右边的这一半。
if(key<arr[min])
max = mid -1; //要找的元素小于中间的元素,我就要mid左边的这一半。
mid = (min + max)>>1; //然后我更新中间值。(因为头指针和尾指针都改变了)
下面是具体的代码:
int halfSearch(int []arr,int key){
int min,max,mid;
min = 0;
max = arr.length-1;
while(min<=max){
mid = (min+max)>>1;
if(key>arr[mid]){
min = mid + 1;
}
else if(key<arr[mid]){
max = mid - 1;
}
else
return mid;
}
return -1; //这里返回-1意识是数组中不存在这个元素。告诉了调用者
}
作者:
Sword
时间:
2013-5-17 17:08
collections工具类集合的元素二分查找——binarySearch()....只能给List集合元素查找
注意:使用二分查找的时候,该集合必须是按自然顺序排过序...
collections.binarySearch(集合,集合中要查找的元素)....会返回查找元素在集合中的角标位置...
如果该集合中的元素不具备比较性(不是comparable接口的子类),那么我们需要自定义个比较器..
collections.binarySearch(集合,集合中要查找的元素,new个自己创建的比较器对象).
你要查找的元素在集合中不存在的话,就会返回 - 1,表示查找结束
作者:
尖卡斌引
时间:
2013-5-17 18:41
刘学明 发表于 2013-5-17 15:47
哪里是负的?
就是返回的地址角标,比如查找的是"chazhao" 在数组的第三号角标,但是返回来的是 -3;这是为什么?
作者:
尖卡斌引
时间:
2013-5-17 18:58
刘学明 发表于 2013-5-17 15:47
哪里是负的?
不好意思说错了,是在插入数据的时候,返回要插入的位置角标,角标一般都是零和正整数。在这里为什么要返回 负的呢?有什么作用和好处?请高手指点。
Collections.jpg
(36.93 KB, 下载次数: 1)
下载附件
2013-5-17 18:56 上传
作者:
王溢君
时间:
2013-5-18 00:36
正的表示找到了。负的表示没有找到嘛。。。本来是返回-1的,后来优化了一下。再负了一个插入点位置。
作者:
Sword
时间:
2013-5-21 09:45
如果问题已经解决了,那么大家请把帖子的类型改为“已解决”,谢谢合作
作者:
占琳
时间:
2013-5-22 09:09
-1一般表示 你要查找元素不存在 还有二分查找的数据最好是有序的 升序或者降序都行
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2