Использование метода двоичного поиска для поиска индекса элемента

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)))