1. import java.util.*;
   
2. public class CollectionsDemo {
   
3. 
   
4.         public static void main(String[] args) {
   
5.                 binarySearchDemo();
   
6.         }
   
7.         public static void binarySearchDemo()
   
8.         {
   
9.                 List<String> list =new ArrayList<String>();
   
10.                 list.add("aafasdfsdfsa");
    
11.                 list.add("bbdfa");
    
12.                 list.add("acdd");
    
13.                 list.add("sddfaxdd");
    
14.                 sop(list);
    
15.                
    
16.                
    
17.                 int index=Collections.binarySearch(list,"acdd");
    
18.                 sop("binarySearch查找的index="+index);
    
19.                
    
20.                 int index1=halfSerach2(list,"acdd",new StrLenComparator());
    
21.                 sop("我的二分法查找到的index为："+index);
    
22.         }
    
23.         public static int halfSerach2(List<String> list,String key,Comparator<String> cmp)
    
24.         {
    
25.                 int max,min,mid;
    
26.                 max=list.size();
    
27.                 min=0;
    
28.                 mid=(max+min)>>1;
    
29.                 while(min<=max)
    
30.                 {
    
31.                         String str=list.get(mid);
    
32.                         int num=cmp.compare(str, key);
    
33.                         if(num>0)
    
34.                                 max=mid-1;
    
35.                         else if(num<0)
    
36.                                 min=mid+1;
    
37.                         else
    
38.                                 return mid;
    
39.                 }
    
40.                 return -min-1;//返回-index-1
    
41.         }
    
42.                 public static void sop(Object obj)
    
43.         {
    
44.                 System.out.println(obj);
    
45.         }
    
46. 
    
47. }
    
48. class StrLenComparator implements Comparator<String>
    
49. {
    
50.         public int compare(String s1,String s2)
    
51.         {
    
52.                 if(s1.length()>s2.length())
    
53.                         return 1;
    
54.                 if(s1.length()<s2.length())
    
55.                         return -1;
    
56.                 return s1.compareTo(s2);
    
57.                        
    
58.         }
    
59. }

复制代码

按说是找不着才会返回一个负的啊


这个“acdd”怎么找不到呢，怎么会是-2呢，其他几个都是正数啊，这是什么情况呢？

1. import java.util.*;
   
2. public class CollectionsDemo {
   
3. 
   
4.         public static void main(String[] args) {
   
5.                 binarySearchDemo();
   
6.         }
   
7.         public static void binarySearchDemo()
   
8.         {
   
9.                 List<String> list =new ArrayList<String>();
   
10.                 list.add("aafasdfsdfsa");
    
11.                 list.add("bbdfa");
    
12.                 list.add("acdd");
    
13.                 list.add("sddfaxdd");
    
14.                 sop(list);
    
15.                
    
16.                 Collections.sort(list);//这里要先排序
    
17.                 int index=Collections.binarySearch(list,"acdd");
    
18.                 sop("binarySearch查找的index="+index);
    
19.                
    
20.                 int index1=halfSerach2(list,"acdd",new StrLenComparator());
    
21.                 sop("我的二分法查找到的index为："+index);
    
22.         }
    
23.         public static int halfSerach2(List<String> list,String key,Comparator<String> cmp)
    
24.         {
    
25.                 int max,min,mid;
    
26.                 max=list.size()-1;//最大角标应该是size-1
    
27.                 min=0;
    
28.                 while(min<=max)
    
29.                 {
    
30.                                                 mid=(max+min)>>1;//这条语句应该在循环中
    
31.                         String str=list.get(mid);
    
32.                         int num=cmp.compare(str, key);
    
33.                         if(num>0)
    
34.                                 max=mid-1;
    
35.                         else if(num<0)
    
36.                                 min=mid+1;
    
37.                         else
    
38.                                 return mid;
    
39.                 }
    
40.                 return -min-1;//返回-index-1
    
41.         }
    
42.                 public static void sop(Object obj)
    
43.         {
    
44.                 System.out.println(obj);
    
45.         }
    
46. 
    
47. }
    
48. class StrLenComparator implements Comparator<String>
    
49. {
    
50.         public int compare(String s1,String s2)
    
51.         {
    
52.                         //这儿不需要对长度进行判断
    
53.                 return s1.compareTo(s2);
    
54.                         
    
55.         }
    
56. }

复制代码

二分法查找最关键的一点一定要记住，查找的序列是有序的！！

xiaoxu 发表于 2013-9-11 00:49
二分法查找最关键的一点一定要记住，查找的序列是有序的！！

鸡冻！写得好详细，灰常感谢，膜拜膜拜！！

xiaoxu 发表于 2013-9-11 00:49
二分法查找最关键的一点一定要记住，查找的序列是有序的！！

最后那里为什么不需要对长度进行判断呢，我是想让人根据长度来进行排序的啊

奔跑的二叉树 发表于 2013-9-11 11:48
最后那里为什么不需要对长度进行判断呢，我是想让人根据长度来进行排序的啊
...

你那方法是在根据长度进行查找，你如果要用这种方式查找，那你首先应该将序列进行这种方式的排序，Collections.sort（）不是这种方式排序的，你可以自己写个方法先按你想要的方式进行排序