- public static void binarySearchDemo()
- {
- List<String> list = new ArrayList<String>();
- list.add("abcd");
- list.add("aaa");
- list.add("zz");
- list.add("kkkkk");
- list.add("qq");
- list.add("z");
- Collections.sort(list,new StrLenComparator());
- sop(list);
- //int index = Collections.binarySearch(list,"aaaa");
- int index = halfSearch(list,"aaa");
- //int index = halfSearch2(list,"aaaa",new StrLenComparator());
- sop("index="+index);
- }
- public static int halfSearch(List<String> list,String key)//二分法原理,获取集合某元素的脚标
- {
- int max,min,mid;
- max = list.size()-1;
- min = 0;
- while(min<=max)
- {
- mid = (max+min)>>1;// /2;
- String 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;
- }
复制代码
哪位大神能帮忙解释一下,当我要查询上面代码list集合下的元素aaa的脚标时,它是怎么用二分法halfSearch(List<String> list,String key)来实现的?对于上面的二分法halfSearch(List<String> list,String key)原理内容想不通,求解~ |
|