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

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 思考。。。 中级黑马   /  2015-7-5 15:43  /  388 人查看  /  0 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

  1. public static void binarySearchDemo()
  2.         {
  3.                 List<String> list = new ArrayList<String>();

  4.                 list.add("abcd");
  5.                 list.add("aaa");
  6.                 list.add("zz");
  7.                 list.add("kkkkk");
  8.                 list.add("qq");
  9.                 list.add("z");
  10.                 Collections.sort(list,new StrLenComparator());

  11.                 sop(list);

  12.                 //int index = Collections.binarySearch(list,"aaaa");
  13.                 int index = halfSearch(list,"aaa");
  14.                 //int index = halfSearch2(list,"aaaa",new StrLenComparator());
  15.                 sop("index="+index);
  16.         }

  17.         public static int halfSearch(List<String> list,String key)//二分法原理,获取集合某元素的脚标
  18.         {
  19.                 int max,min,mid;
  20.                 max = list.size()-1;
  21.                 min = 0;

  22.                 while(min<=max)
  23.                 {
  24.                         mid = (max+min)>>1;//  /2;

  25.                         String str = list.get(mid);

  26.                         int num = str.compareTo(key);
  27.                         if(num>0)
  28.                                 max = mid -1;
  29.                         else if(num<0)
  30.                                 min = mid + 1;
  31.                         else
  32.                                 return mid;
  33.                 }
  34.                 return -min-1;
  35.         }
复制代码


哪位大神能帮忙解释一下,当我要查询上面代码list集合下的元素aaa的脚标时,它是怎么用二分法halfSearch(List<String> list,String key)来实现的?对于上面的二分法halfSearch(List<String> list,String key)原理内容想不通,求解~

0 个回复

您需要登录后才可以回帖 登录 | 加入黑马