A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 庄星睿 中级黑马   /  2012-7-1 18:07  /  1592 人查看  /  5 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 庄星睿 于 2012-7-1 19:44 编辑

重写二分法查找
  1. import java.util.*;

  2. class CollectionsDemo2
  3. {
  4. public static void main(String[] args)
  5. {
  6. List<String> ls=new ArrayList<String>();
  7. ls.add("aaa");
  8. ls.add("aD");
  9. ls.add("bcad");
  10. ls.add("bfgfsdf");
  11. ls.add("cdesf");
  12. ls.add("zz");
  13. System.out.println(ls);
  14. Collections.sort(ls);
  15. System.out.println(ls);
  16. int index=Tools.halfSearch(ls,"aaaa");
  17. System.out.println(index);
  18. }


  19. }

  20. class Tools
  21. {
  22. public static <T> int halfSearch(List<? extends Comparable<? super T>> list, T key)
  23. {
  24. int min=0,max=list.size()-1,mid;
  25. while(min<=max)
  26. {
  27. mid=(min+max)>>1;
  28. T str=list.get(mid);      //这里提示报错
  29. int num=str.compareTo(key);  //这里提示报错
  30. if(num>0)
  31.        max=mid-1;
  32. else if(num<0)
  33.        min=mid+1;
  34. else
  35. return mid;
  36. }
  37. return -min-1;

  38. }
  39. }
复制代码
这个程序我用重新传比较器的写没问题:
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
    }

评分

参与人数 1技术分 +1 收起 理由
刘蕴学 + 1

查看全部评分

5 个回复

倒序浏览
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了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马