黑马程序员技术交流社区

标题: Collecitions类的binsarySearch()方法有疑问。 [打印本页]

---

作者: 何俊森    时间: 2013-4-14 21:12
标题: Collecitions类的binsarySearch()方法有疑问。

1. import java.util.ArrayList;
   
2. import java.util.Collections;
   
3. import java.util.List;
   
4. 
   
5. public class CollectionDemo04 {
   
6.         public static void main(String[] args) {
   
7.                 List<String> all = new ArrayList<String>();
   
8.                 Collections.addAll(all, "klaus", "jacob", "tome", "df");
   
9.                 int point1 = Collections.binarySearch(all, "tome");
   
10.                 System.out.println("检索结果：" + point1);
    
11.                 int point2 = Collections.binarySearch(all, "df");
    
12.                 System.out.println("检索结果：" + point2);
    
13.                 int point3 = Collections.binarySearch(all, "klaus");
    
14.                 System.out.println("检索结果：" + point3);
    
15.                 int point4 = Collections.binarySearch(all, "dffdf");
    
16.                 System.out.println("检索结果：" + point4);
    
17.         }
    
18. 
    
19. }

复制代码

binarySearch()方法如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引；如果列表中的所有元素都小于指定的键，则为 list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。：这里那元素索引是怎么计算的？还有那个程序结果怎么回事，point3和point2不应该是负数啊

QQ截图20130414205656.png (5.65 KB, 下载次数: 64)

下载附件

2013-4-14 21:06 上传

---

作者: 刘策    时间: 2013-4-14 21:26
使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据指定的比较器对列表进行升序排序（通过 sort(List, Comparator) 方法）。如果没有对列表进行排序，则结果是不确定的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。
这个是排序后的结果
[df, jacob, klaus, tome]
检索结果：3
检索结果：0
检索结果：2
检索结果：-2

---

作者: 殇_心。    时间: 2013-4-14 21:31
原因应该是你没排序的结果。 这个你存储之前  排个序就ok了。

---

作者: love_java    时间: 2013-4-14 21:32
binarySearch
public static <T> int binarySearch(List<? extends Comparable<? super T>> list,T key)
使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据列表元素的自然顺序对列表进行升序排序（通过 sort(List) 方法）。如果没有对列表进行排序，则结果是不确定的。如果列表包含多个等于指定对象的元素，则无法保证找到的是哪一个。
此方法对“随机访问”列表运行 log(n) 次（它提供接近固定时间的位置访问）。如果指定列表没有实现 RandomAccess 接口并且是一个大型列表，则此方法将执行基于迭代器的二分搜索，执行 O(n) 次链接遍历和 O(log n) 次元素比较。

上面是api上说的，把你的程序改成整型运行了一下，结果是对的。

1. package test;
   
2. import java.util.ArrayList;
   
3. import java.util.Collections;
   
4. import java.util.List;
   
5. 
   
6. public class CollectionDemo04 {
   
7.         public static void main(String[] args) {
   
8.                 List<Integer> all = new ArrayList<Integer>();
   
9.                 Collections.addAll(all, 4, 12, 26, 48);
   
10.                 int point1 = Collections.binarySearch(all, 12);
    
11.                 System.out.println("检索结果：" + point1);
    
12.                 int point2 = Collections.binarySearch(all, 26);
    
13.                 System.out.println("检索结果：" + point2);
    
14.                 int point3 = Collections.binarySearch(all, 1);
    
15.                 System.out.println("检索结果：" + point3);
    
16.                 int point4 = Collections.binarySearch(all, 4);
    
17.                 System.out.println("检索结果：" + point4);
    
18.         }
    
19. 
    
20. }

复制代码

运行结果：

检索结果：1
检索结果：2
检索结果：-1
检索结果：0

---

作者: 何俊森    时间: 2013-4-14 21:32

刘策 发表于 2013-4-14 21:26
使用二分搜索法搜索指定列表，以获得指定对象。在进行此调用之前，必须根据指定的比较器对列表进行升序排序 ...

最后一个-2怎么计算得到的？

---

作者: 刘策    时间: 2013-4-14 23:36
-插入点-1==-2，所以这个插入点，就等于1（-插入== -2+1）其实这个二分查找低层用的就是HalfSearch（折半查找，）老师说的，

---

作者: 何俊森    时间: 2013-4-15 15:26

刘策 发表于 2013-4-14 23:36
-插入点-1==-2，所以这个插入点，就等于1（-插入== -2+1）其实这个二分查找低层用的就是HalfSearch（折半查 ...

谢谢、:handshake

---

作者: 刘策    时间: 2013-4-15 16:50

何俊森 发表于 2013-4-15 15:26
谢谢、

共同进步

---

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

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