使用二进制搜索方法查找项目的索引

Question

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

Class

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，函数仍然是 returns -1。我在此功能中进行比较的正确方法是什么？如有必要，我还可以提供更多代码，我包含了所有我认为相关的代码。

Answer 1

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

if ((int) x == mid)

你想要：

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

使用二进制搜索方法查找项目的索引

Using the Binary Search method to find the index of an Item

java

list

binary-search