黑马程序员技术交流社区

标题: Collections.binarySearch的问题 [打印本页]
作者: 奔跑的二叉树    时间: 2013-9-11 00:03
标题: Collections.binarySearch的问题
本帖最后由 奔跑的二叉树 于 2013-9-11 00:12 编辑
  1. import java.util.*;
  2. public class CollectionsDemo {

  4.         public static void main(String[] args) {
  5.                 binarySearchDemo();
  6.         }
  7.         public static void binarySearchDemo()
  8.         {
  9.                 List<String> list =new ArrayList<String>();
  10.                 list.add("aafasdfsdfsa");
  11.                 list.add("bbdfa");
  12.                 list.add("acdd");
  13.                 list.add("sddfaxdd");
  14.                 sop(list);
  15.                
  16.                
  17.                 int index=Collections.binarySearch(list,"acdd");
  18.                 sop("binarySearch查找的index="+index);
  19.                
  20.                 int index1=halfSerach2(list,"acdd",new StrLenComparator());
  21.                 sop("我的二分法查找到的index为："+index);
  22.         }
  23.         public static int halfSerach2(List<String> list,String key,Comparator<String> cmp)
  24.         {
  25.                 int max,min,mid;
  26.                 max=list.size();
  27.                 min=0;
  28.                 mid=(max+min)>>1;
  29.                 while(min<=max)
  30.                 {
  31.                         String str=list.get(mid);
  32.                         int num=cmp.compare(str, key);
  33.                         if(num>0)
  34.                                 max=mid-1;
  35.                         else if(num<0)
  36.                                 min=mid+1;
  37.                         else
  38.                                 return mid;
  39.                 }
  40.                 return -min-1;//返回-index-1
  41.         }
  42.                 public static void sop(Object obj)
  43.         {
  44.                 System.out.println(obj);
  45.         }

  47. }
  48. class StrLenComparator implements Comparator<String>
  49. {
  50.         public int compare(String s1,String s2)
  51.         {
  52.                 if(s1.length()>s2.length())
  53.                         return 1;
  54.                 if(s1.length()<s2.length())
  55.                         return -1;
  56.                 return s1.compareTo(s2);
  57.                        
  58.         }
  59. }
复制代码
按说是找不着才会返回一个负的啊


这个“acdd”怎么找不到呢，怎么会是-2呢，其他几个都是正数啊，这是什么情况呢？
作者: xiaoxu    时间: 2013-9-11 00:49
  1. import java.util.*;
  2. public class CollectionsDemo {

  4.         public static void main(String[] args) {
  5.                 binarySearchDemo();
  6.         }
  7.         public static void binarySearchDemo()
  8.         {
  9.                 List<String> list =new ArrayList<String>();
  10.                 list.add("aafasdfsdfsa");
  11.                 list.add("bbdfa");
  12.                 list.add("acdd");
  13.                 list.add("sddfaxdd");
  14.                 sop(list);
  15.                
  16.                 Collections.sort(list);//这里要先排序
  17.                 int index=Collections.binarySearch(list,"acdd");
  18.                 sop("binarySearch查找的index="+index);
  19.                
  20.                 int index1=halfSerach2(list,"acdd",new StrLenComparator());
  21.                 sop("我的二分法查找到的index为："+index);
  22.         }
  23.         public static int halfSerach2(List<String> list,String key,Comparator<String> cmp)
  24.         {
  25.                 int max,min,mid;
  26.                 max=list.size()-1;//最大角标应该是size-1
  27.                 min=0;
  28.                 while(min<=max)
  29.                 {
  30.                                                 mid=(max+min)>>1;//这条语句应该在循环中
  31.                         String str=list.get(mid);
  32.                         int num=cmp.compare(str, key);
  33.                         if(num>0)
  34.                                 max=mid-1;
  35.                         else if(num<0)
  36.                                 min=mid+1;
  37.                         else
  38.                                 return mid;
  39.                 }
  40.                 return -min-1;//返回-index-1
  41.         }
  42.                 public static void sop(Object obj)
  43.         {
  44.                 System.out.println(obj);
  45.         }

  47. }
  48. class StrLenComparator implements Comparator<String>
  49. {
  50.         public int compare(String s1,String s2)
  51.         {
  52.                         //这儿不需要对长度进行判断
  53.                 return s1.compareTo(s2);
  54.                         
  55.         }
  56. }
复制代码
二分法查找最关键的一点一定要记住，查找的序列是有序的！！
作者: 奔跑的二叉树    时间: 2013-9-11 11:46
xiaoxu 发表于 2013-9-11 00:49
二分法查找最关键的一点一定要记住，查找的序列是有序的！！

鸡冻！写得好详细，灰常感谢，膜拜膜拜！！
作者: 奔跑的二叉树    时间: 2013-9-11 11:48
xiaoxu 发表于 2013-9-11 00:49
二分法查找最关键的一点一定要记住，查找的序列是有序的！！

最后那里为什么不需要对长度进行判断呢，我是想让人根据长度来进行排序的啊
作者: xiaoxu    时间: 2013-9-11 14:09
奔跑的二叉树 发表于 2013-9-11 11:48
最后那里为什么不需要对长度进行判断呢，我是想让人根据长度来进行排序的啊
...

你那方法是在根据长度进行查找，你如果要用这种方式查找，那你首先应该将序列进行这种方式的排序，Collections.sort（）不是这种方式排序的，你可以自己写个方法先按你想要的方式进行排序




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