重写二分法查找

1. import java.util.*;
   
2. 
   
3. class CollectionsDemo2
   
4. {
   
5. public static void main(String[] args)
   
6. {
   
7. List<String> ls=new ArrayList<String>();
   
8. ls.add("aaa");
   
9. ls.add("aD");
   
10. ls.add("bcad");
    
11. ls.add("bfgfsdf");
    
12. ls.add("cdesf");
    
13. ls.add("zz");
    
14. System.out.println(ls);
    
15. Collections.sort(ls);
    
16. System.out.println(ls);
    
17. int index=Tools.halfSearch(ls,"aaaa");
    
18. System.out.println(index);
    
19. }
    
20. 
    
21. 
    
22. }
    
23. 
    
24. class Tools
    
25. {
    
26. public static <T> int halfSearch(List<? extends Comparable<? super T>> list, T key)
    
27. {
    
28. int min=0,max=list.size()-1,mid;
    
29. while(min<=max)
    
30. {
    
31. mid=(min+max)>>1;
    
32. T str=list.get(mid);      //这里提示报错
    
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. 
    
43. }
    
44. }

复制代码

这个程序我用重新传比较器的写没问题：
public static <T> int halfSearch2(List<? extends T> list, T key,Comparator<? super T> comp)
按照传比较器的写的没问题，但按照继承Comparable接口会提示报错，我在定义的泛型的时候，就已经定义了他必须传Comparable的子类对象，那他肯定具备compareTo
的方法的，那么T str=list.get(mid); int num=key.compareTo(str),应该是可以比较的.....求解

刚看了源码，找到问题了，定义泛型就是为了避免强转，还是泛型那除了问题
T  str=list.get(mid);  //这样写相当于把类型提升了
Comparable<? super T> T=list.get(mid);这样写就ok了，因为list集合里的对象一定是Comparable接口的子类对象。
还有比较顺序问题
int num=key.compareTo(str);这样写ok，因为key可以使Object类型，API在形参里定义的是 T key)
int num=str.compareTo(key); str是Comparable接口的子类对象，一定具备compareTo方法

下面是源码：
private static <T>
    int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key)
    {
        int low = 0;
        int high = list.size()-1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            Comparable<? super T> midVal = list.get(mid);
            int cmp = midVal.compareTo(key);
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid; // key found
        }
        return -(low + 1);  // key not found
    }

32行 T str =list.get(mid)这句当然会报错了啊，因为T只是对类或方法泛型的一个表示，当真正使用的时候，一定要给定
真实的类型啊
while(min<=max)
{
mid=(min+max)>>1;
String  str=list.get(mid);      //改成这样
int num=key.compareTo(str);  //这里提示报错
if(num>0)
min=mid+1;
else if(num<0)
max=mid-1;
else
return mid;
}

compareTo是String的一个方法你那样去调用肯定不行，因为泛型的类型未知传进来的东西不一定是String。还有泛型不能那样用，同样的泛型的类型未知而方法的返回值是实现就有的所以如果你的代码可以不报错的话这样改是可以的：
Object str =  (T)list.get(mid);      //强转
int num=((String) key).compareTo((String) str);  //强转

不过说实话楼主 我觉得这样做并没有什么意义，貌似你的程序里就是要比较两个String是否一样，如果是这样为何不传进来的时候就把类型设置成String
没有必要用泛型吧。

Forever。 发表于 2012-7-1 19:07
compareTo是String的一个方法你那样去调用肯定不行，因为泛型的类型未知传进来的东西不一定是String。还有 ...

定义泛型的作用就是避免强转，呵呵

庄星睿 发表于 2012-7-1 19:31
定义泛型的作用就是避免强转，呵呵

一边是方法有具体的返回值，另一侧当然不能用泛型，你没有看懂代码。

Forever。 发表于 2012-7-1 19:36
一边是方法有具体的返回值，另一侧当然不能用泛型，你没有看懂代码。

可以的，刚看了源码，找到问题了
Comparable<? super T> str=list.get(mid);
OK了