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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© kira 中级黑马   /  2014-1-27 17:34  /  923 人查看  /  1 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

我现在自己定一个折半查找 方法写好了 运行通过了 发现角标有的对 有的不对
而且 我用Collcetions.sort方法里面传比较器能用
我在我的方法里传比较器 比较的却还是默认比较器的比较方式
我的比较方式是按照字符串长度排序
下面是我的代码
  1. import java.util.ArrayList;
  2. import java.util.Collection;
  3. import java.util.Collections;
  4. import java.util.Comparator;
  5. import java.util.List;

  6. public class ListDemoC {

  7.         /**
  8.          * @param args
  9.          */
  10.         public static void main(String[] args) {
  11.                 // TODO Auto-generated method stub
  12.                 List<String> arraylist = new ArrayList<String>();
  13.                 arraylist.add("java");
  14.                 arraylist.add("hello");
  15.                 arraylist.add("www");
  16. //                maxShow();
  17.                  int i1 =myHalfSearch(arraylist,"ww",new mycomHalf());
  18.                 System.out.println(arraylist);
  19.                  System.out.println(i1);
  20.                  Collections.sort(arraylist, new mycomHalf());
  21.                  System.out.println(arraylist);
  22.         }
  23.         public static void maxShow(){//原先的折半查找
  24.                 List<String> al = new ArrayList<String>();
  25.                 al.add("java");
  26.                 al.add("hello");
  27.                 al.add("www");
  28.                 String s = Collections.max(al);
  29.                 int i = Collections.binarySearch(al, "java");
  30.         System.out.println(al);//打印最大值
  31.                 System.out.println(i);//打印角标数
  32.         }
  33.        
  34.         //制造我自己的折半查找的方法
  35.         public static int myHalfSearch(List<String> list,String key,mycomHalf com){
  36.                 int max,min,mid;
  37.                 max = list.size()-1;
  38.                 min=0;
  39.                
  40.                 while(min<=max){
  41.                         mid=(max+min)>>1;//这句话相当于相加除以2
  42.                         //获取到中间的角标
  43.                         String s = list.get(mid);//已经获取到中间角标
  44.                         int num= com.compare(s, key);//比较一下
  45.                         if(num>0){
  46.                                 max = mid-1;
  47.                                
  48.                         }
  49.                         else if(num<0){
  50.                                
  51.                                 min = mid+1;
  52.                                
  53.                         }
  54.                         else{
  55.                         return mid;
  56.                         }
  57.                        
  58.                 }
  59.        
  60.                 return -min-1;//返回插入点-1
  61.                
  62.         }

  63. }
  64. class mycomHalf implements Comparator<String>{//我自己的比较器

  65.        
  66.         public int compare(String s1, String s2) {
  67.                  return new Integer(s1.length()).compareTo(new Integer(s2.length()));//按照长度进行比较
  68.                 // TODO Auto-generated method stub
  69.                
  70.         }
  71.        
  72.        
  73.        
  74. }
复制代码
我验证了一下 当传入java 和hello的时候 角标没错 但传入了www角标却不正确了
而且 还有我的方法没有实现我自己比较器的比较方式 Collcetions.sort方法传入的比较器却成功了 这是为什么呢 求指教{:soso_e136:}


评分

参与人数 1技术分 +1 收起 理由
ily521125 + 1

查看全部评分

1 个回复

倒序浏览
折半查找是有前提的,要保证查找的源必须是有序的,你给出的代码就不具备此前提,何谈折半呢?
另外打开你的maxShow()函数打印的角标也不对,原理上这个运行也对不了。
如有不当,请指正  

评分

参与人数 1技术分 +1 收起 理由
ily521125 + 1

查看全部评分

回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马