java - 使用二分查找方法查找项目的索引

Question

所以我要把两个函数从使用顺序搜索重写为二分搜索。我了解两者之间的效率差异，但是，在将它们更改为二进制时，我在语法上遇到了问题。

类别

public class SortedList<Item extends Comparable<Item>> implements SortedList<Item> {

    private Object[] data = new Object[5];

    private int size = 0;

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean equals(Object o) {
        SortedList<Item> lst = (SortedList<Item>) o;
        if (size != lst.size)
            return false;
        Iterator<Item> i1 = lst.iterator();
        Iterator<Item> i2 = iterator();
        while (i1.hasNext()) {
            Item x1 = i1.next();
            Item x2 = i2.next();
            if (!x1.equals(x2))
                return false;
        }
        return true;
    }

    //METHOD TO CHANGE TO BINARY-SEARCH
    public int indexOf(Item x) {
         int low = 0, high = size - 1;
         while (low <= high) {
            int mid = (low + high) / 2;
            if ((int) x == mid)
                return mid;
            else if ((int) x > mid)
                high = mid - 1;
            else
                low = mid + 1;
        }
        return -1;
     }

主要

public class Main {

    public static void main(String[] args) {

        SortedList<Integer> s = new SortedList<Integer>();

        s.add(5);
        s.add(6);
        s.add(7);
        s.add(8);
        s.add(9);
        s.add(10);

        System.out.println(s.indexOf(6)); //-1

    }
}

基本上，我在将 Item x 与整数进行比较时遇到问题。似乎即使当我将 x 转换为 Int 时，该函数仍然返回 -1。我在这个函数中比较的正确方法是什么？如果有必要，我还可以提供更多代码，我包含了我认为相关的所有代码。

Answer 1

您混淆了列表中的索引和元素:

if ((int) x == mid)

你想要:

if(x.equals(itemAtIndex(mid)))