黑马程序员技术交流社区

标题: Collections类的相关问题 [打印本页]

---

作者: 思考。。。    时间: 2015-7-5 15:43
标题: Collections类的相关问题

1. public static void binarySearchDemo()
   
2.         {
   
3.                 List<String> list = new ArrayList<String>();
   
4. 
   
5.                 list.add("abcd");
   
6.                 list.add("aaa");
   
7.                 list.add("zz");
   
8.                 list.add("kkkkk");
   
9.                 list.add("qq");
   
10.                 list.add("z");
    
11.                 Collections.sort(list,new StrLenComparator());
    
12. 
    
13.                 sop(list);
    
14. 
    
15.                 //int index = Collections.binarySearch(list,"aaaa");
    
16.                 int index = halfSearch(list,"aaa");
    
17.                 //int index = halfSearch2(list,"aaaa",new StrLenComparator());
    
18.                 sop("index="+index);
    
19.         }
    
20. 
    
21.         public static int halfSearch(List<String> list,String key)//二分法原理，获取集合某元素的脚标
    
22.         {
    
23.                 int max,min,mid;
    
24.                 max = list.size()-1;
    
25.                 min = 0;
    
26. 
    
27.                 while(min<=max)
    
28.                 {
    
29.                         mid = (max+min)>>1;//  /2;
    
30. 
    
31.                         String str = list.get(mid);
    
32. 
    
33.                         int num = str.compareTo(key);
    
34.                         if(num>0)
    
35.                                 max = mid -1;
    
36.                         else if(num<0)
    
37.                                 min = mid + 1;
    
38.                         else
    
39.                                 return mid;
    
40.                 }
    
41.                 return -min-1;
    
42.         }

复制代码

哪位大神能帮忙解释一下，当我要查询上面代码list集合下的元素aaa的脚标时，它是怎么用二分法halfSearch(List<String> list,String key)来实现的？对于上面的二分法halfSearch(List<String> list,String key)原理内容想不通，求解~

---

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

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