黑马程序员技术交流社区

标题: 二分搜索法排序 [打印本页]

---

作者: 殷婷婷    时间: 2013-11-15 10:41
标题: 二分搜索法排序

1. import java.util.ArrayList;
   
2. import java.util.Collections;
   
3. import java.util.Comparator;
   
4. import java.util.List;
   
5. 
   
6. 
   
7. public class Test {
   
8. 
   
9.         public static void main(String[] args) {
   
10.                 // TODO Auto-generated method stub
    
11.                 List<String> list = new ArrayList<String>();
    
12.                 list.add("java");
    
13.                 list.add("demo");
    
14.                 list.add("yinyi");
    
15.                 list.add("zo");
    
16.                 list.add("demo");
    
17.                 Collections.sort(list,new StrLenComparator1());
    
18.                 System.out.println(list);
    
19.                 System.out.println(halfSearch2(list,"zo",new StrLenComparator1()));
    
20.         }
    
21.         public static int halfSearch2(List<String> list,String key,Comparator<String> cmp)
    
22.         {
    
23.                 int min,max,mid;
    
24.                 max = list.size()-1;
    
25.                 min = 0;
    
26.                 while(min<=max)
    
27.                 {
    
28.                         mid = (min+max)>>1;
    
29.                         String str = list.get(mid);
    
30.                         int num = cmp.compare(str,key);
    
31.                         if(num>0)
    
32.                                 max = mid - 1;
    
33.                         if(num<0)
    
34.                                 min = mid + 1;
    
35.                         else return mid;
    
36.                 }
    
37.                 return -min-1;
    
38.         }
    
39. }
    
40. class StrLenComparator1 implements Comparator<String>
    
41. {
    
42.         public int compare(String s1,String s2)
    
43.         {
    
44.                 if(s1.length()>s2.length()) return 1;
    
45.                 if(s1.length()<s2.length()) return -1;
    
46.                 return s1.compareTo(s2);
    
47.         }
    
48. }
    
49.         
    

复制代码

按照二分搜索法排序，System.out.println(halfSearch2(list,"zo",new StrLenComparator1()));的结果应该是0，可是运行了下，输出是2，实在找不出哪里错了，用binarySearch(list,"zo",new StrLenComparator()))输出的是正确的，肯定是程序哪儿写错了，麻烦帮我看一下，到底是哪儿的错。

---

作者: linjl_ll    时间: 2013-11-15 11:03
我们来分析下下面的代码，第一次执行循环时如下
while(min<=max)
                {
                        mid = (min+max)>>1;//mid =2
                        String str = list.get(mid);//str的值为"demo"
                        int num = cmp.compare(str,key);//返回值大于0即num>0
                        if(num>0)//这个if语句会执行num>0
                                max = mid - 1;//max=1
                        if(num<0)//这个if不会执行，所以他后面的else会执行
                                min = mid + 1;
                        else return mid;//返回mid即2
                }

你的第二个if语句应该是else if。

---

作者: lichao    时间: 2013-11-15 11:42

1. import java.util.ArrayList;
   
2. import java.util.Collections;
   
3. import java.util.Comparator;
   
4. import java.util.List;
   
5. 
   
6. 
   
7. public class Test {
   
8. 
   
9.         public static void main(String[] args) {
   
10.                 // TODO Auto-generated method stub
    
11.                 List<String> list = new ArrayList<String>();
    
12.                 list.add("java");
    
13.                 list.add("demo");
    
14.                 list.add("yinyi");
    
15.                 list.add("zo");
    
16.                 list.add("demo");
    
17.                 Collections.sort(list,new StrLenComparator1());
    
18.                 System.out.println(list);
    
19.                 System.out.println(halfSearch2(list,"zo",new StrLenComparator1()));
    
20.         }
    
21.         public static int halfSearch2(List<String> list,String key,Comparator<String> cmp)
    
22.         {
    
23.                 int min,max,mid;
    
24.                 max = list.size()-1;
    
25.                 min = 0;
    
26.                 while(min<=max)
    
27.                 {
    
28.                         mid = (min+max)>>1;
    
29.                         String str = list.get(mid);
    
30.                         int num = cmp.compare(str,key);
    
31.                         if(num>0)
    
32.                                 max = mid - 1;
    
33.                         else if(num<0)  //少写了一个else   //如果比较值是大于0的数，在上面的if比较后 ，又在此if比较，由于num大于0，所以执行else 程序结束输出返回值2；
    
34.                                 min = mid + 1;
    
35.                         else return mid;
    
36.                 }
    
37.                 return -min-1;
    
38.         }
    
39. }
    
40. class StrLenComparator1 implements Comparator<String>
    
41. {
    
42.         public int compare(String s1,String s2)
    
43.         {
    
44.                 if(s1.length()>s2.length()) return 1;
    
45.                 if(s1.length()<s2.length()) return -1;
    
46.                 return s1.compareTo(s2);
    
47.         }
    
48. }
    
49.         
    

复制代码

---

作者: 殷婷婷    时间: 2013-11-15 12:08

linjl_ll 发表于 2013-11-15 11:03
我们来分析下下面的代码，第一次执行循环时如下
while(min>1;//mid =2
                        String str ...

是的哦，谢谢啦，哈哈:victory:

---

作者: 殷婷婷    时间: 2013-11-15 12:09

lichao 发表于 2013-11-15 11:42

谢谢帮助啊:victory:

---

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

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