本帖最后由 庄星睿 于 2012-7-1 19:44 编辑
重写二分法查找- import java.util.*;
- class CollectionsDemo2
- {
- public static void main(String[] args)
- {
- List<String> ls=new ArrayList<String>();
- ls.add("aaa");
- ls.add("aD");
- ls.add("bcad");
- ls.add("bfgfsdf");
- ls.add("cdesf");
- ls.add("zz");
- System.out.println(ls);
- Collections.sort(ls);
- System.out.println(ls);
- int index=Tools.halfSearch(ls,"aaaa");
- System.out.println(index);
- }
- }
- class Tools
- {
- public static <T> int halfSearch(List<? extends Comparable<? super T>> list, T key)
- {
- int min=0,max=list.size()-1,mid;
- while(min<=max)
- {
- mid=(min+max)>>1;
- T str=list.get(mid); //这里提示报错
- int num=str.compareTo(key); //这里提示报错
- if(num>0)
- max=mid-1;
- else if(num<0)
- min=mid+1;
- else
- return mid;
- }
- return -min-1;
- }
- }
复制代码 这个程序我用重新传比较器的写没问题:
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
}
|