黑马程序员技术交流社区

标题: 关于Collections工具类中的binarySearch方法的问题 [打印本页]

---

作者: 唐巍    时间: 2012-3-24 02:16
标题: 关于Collections工具类中的binarySearch方法的问题
请看代码：
import java.util.*;
class CollectionsDemo3
{
        public static void main(String[] args)
        {
                binarySearchDemo();
        }
        public static void sop(Object obj)
        {
                System.out.println(obj);
        }
        public static void binarySearchDemo()
        {
                List<String> list=new ArrayList<String>();
                list.add("acv");
                list.add("bsd");
                list.add("kjdaaa");
                list.add("qq");
                list.add("x");
                list.add("qq");
                Collections.sort(list);
                sop(list);
                int index=Collections.binarySearch(list,"fgh");
                sop("index="+index);//打印结果：-3   集合中没找到"fgh"元素，为什么返回-3？不返回-1呢？
        }
}

---

作者: 刘元霄    时间: 2012-3-24 02:38
int index=Collections.binarySearch(list,"fgh");
返回的是fgh 的角标位，如果没有该元素否则返回 (-(插入点) - 1)。
  你算一下 该集合中没有fgh的元素，然后会直接返回它的插入点  应该是 2  然后  -2-1 =-3  所以返回 -3  
能理解吗？

---

作者: 刘元霄    时间: 2012-3-24 02:42
多打了个否。。。。。
就是 -（插入点）  再-1 一次  你算一下就 能理解的

---

作者: 贠(yun)靖    时间: 2012-3-24 04:38
  以后遇到这种情况 建议你看一下api   里面介绍的很清楚的  
   我们不可能把每个方法的返回类型和怎么返回的 都记清楚   也不太现实  所以查api是个好习惯啊  亲
如果搜索键包含在列表中，则返回搜索键的索引；否则返回 (-(插入点) - 1)。插入点 被定义为将键插入列表的那一点：即第一个大于此键的元素索引；如果列表中的所有元素都小于指定的键，则为 list.size()。注意，这保证了当且仅当此键被找到时，返回的值将 >= 0。
      插入点就是说 你要查找的那个字符串没有  但是他的大小刚好排在你的集合中的2角标哪   -2-1 就是-3  你可以试一试  查一个没有的字符串  但是这个字符串是最小的 他就返回-1 了

---

作者: liumeng    时间: 2012-3-24 06:05
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
    }
在进入while时low变成了2

---

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

黑马程序员IT技术论坛 X3.2