java - 使用binarySearch在ArrayList中查找对象

Question

我在 ArrayList 中搜索对象时遇到问题。

这是我到目前为止的代码:

public static int binarySearch( ArrayList list, Object key ) {
    Comparable comp = (Comparable)key;

    int res = -1, min = 0, max = list.size() - 1, pos;
    while( ( min <= max ) && ( res == -1 ) ) {
        pos = (min + max) / 2;
        int comparison = comp.compareTo(pos);
        if( comparison == 0)
            res = pos;
        else if( comparison < 0)
            max = pos - 1;
        else
            min = pos + 1;
    }
    return res;
}

这是我的测试:

public static void main(String[] args) {
    ArrayList list = new ArrayList();
    list.add(new String("February"));
    list.add(new String("January"));
    list.add(new String("June"));
    list.add(new String("March"));

    System.out.println(list);

    Object obj = new String("February");

    int index = binarySearch(list, obj);

    System.out.println(obj + " is at index" + index);

}

程序总是返回-1，这意味着它永远找不到它正在搜索的对象？您看到任何错误吗？或者我错误地测试了搜索？

Answer 1

您将 comp 与 pos 进行比较，这就像比较 Comparable(在本例中为 String >) 带有整数:

int comparison = comp.compareTo(pos);

您应该改为检索列表中 pos 索引中的元素并使用该元素进行比较:

int comparison = comp.compareTo(list.get(pos));