Бинарный поиск строки в связанном списке

Question

Мне нужно выполнить двоичный поиск в связанном списке с различными типами данных. Код ниже не будет компилироваться. Кажется, я не могу заставить compareTo() работать.

Вот связанный список класса:

public class Contributor { 

private String firstName; 
private String lastName; 
private String country; 
private String phone; 
private double contribution; 
private int id;} 

Метод двоичного поиска ниже. Поиск должен найти определенное имя lastName, используя метод двоичного поиска.

public void binarySearch(List<Contributor> l, String key) { 
    System.out.println("Binary search."); 

    int upperBound = l.size(); 
    int lowerBound = 1; 
    int midpoint = (upperBound + lowerBound)/2; 
    int difference = upperBound - lowerBound; 

    for (int i = 0; i < l.size(); i++) { 
     if (key.compareTo(l.get(midpoint - 1))&& difference != 1) { 
      upperBound = midpoint - 1; 
      midpoint = upperBound/2; 
     } else if (key.compareTo(l.get(midpoint - 1)) && difference != 1) { 
      lowerBound = midpoint + 1; 
      midpoint = (lowerBound + upperBound)/2; 

     } else if (key.equals(l.get(midpoint - 1))) { 
      midpoint = midpoint - 1; 

      System.out.println("We found " + key + " at position " + midpoint + " in the list."); 
      i = l.size(); 
     } else { 
      System.out.println("We couldn't find " + key + " in the list."); 
      i = l.size(); 
     } 
    } 
} 

Answer 1

По Глядя на ваш код l.get (средняя точка-1) возвращает объект Вкладчик не строка, а метод key.compareTo может принимать только аргумент типа String.

Answer 2

Функция compareTo() возвращает целочисленное значение. поэтому попробуйте

if(key.compareTo(str) < 0) 

или

if(key.compareTo(str) > 0) 

или

if(key.compareTo(str) == 0) 

также сравнить его с строки из класса Загрузил, а не с самим классом. что

if(key.compareTo((l.get(midpoint - 1)).firstName)<0) 

другая логическая ошибка, когда вы делаете

midpoint = upperBound/2; 

вы предполагая lowerbound быть . Но его значение может измениться итерациями. Поэтому учтите, что также

Answer 3

Здесь есть логическая ошибка - как говорит Акшай, ваш ключ String, поэтому нет смысла искать его в списке Contibutor s - вам нужно будет найти Contributor.

Более этого, хотя, является предварительным условием для бинарного поиска является то, что список отсортирован, который требует, чтобы ваш Contributor объекта будет Comparable (или, по крайней мере, что вы передаете Comparator.

Я изменил свой код решить эти проблемы:

class Contributor implements Comparable<Contributor>{ 

    private String firstName; 
    private String lastName; 
    private String country; 
    private String phone; 
    private double contribution; 
    private int id; 

    public int compareTo(Contributor o) { 
     return Integer.valueOf(id).compareTo(o.id); 
    } 
} 

public class BinarySearch { 
    /** 
    * Performs a binary search for <code>key</code> in the list <code>l</code>. 
    * 
    * @param l Ordered list of Contributors. 
    * @param key Value to search for. 
    */ 
    public void binarySearch(List<Contributor> l, Contributor key) { 
     System.out.println("Binary search."); 

     int upperBound = l.size(); 
     int lowerBound = 1; 
     int midpoint = (upperBound + lowerBound)/2; 
     int difference = upperBound - lowerBound; 

     for (int i = 0; i < l.size(); i++) { 
      if (key.compareTo(l.get(midpoint - 1)) <0) { 
       upperBound = midpoint - 1; 
       midpoint = upperBound/2; 
      } else if (key.compareTo(l.get(midpoint - 1))>0) { 
       lowerBound = midpoint + 1; 
       midpoint = (lowerBound + upperBound)/2; 

      } else if (key.equals(l.get(midpoint - 1))) { 
       midpoint = midpoint - 1; 

       System.out.println("We found " + key + " at position " 
         + midpoint + " in the list."); 
       i = l.size(); 
      } else { 
       System.out.println("We couldn't find " + key + " in the list."); 
       i = l.size(); 
      } 
     } 
    } 
} 

Это должно исправить вашу ошибку компиляции, хотя, как другие отмечают, логика поиска сама имеет некоторые ошибки Пожалуйста, обратите внимание также, что предпосылкой метода binarySearch является то, что список можно заказать, и это. требование должно быть документом nted. Я добавил комментарий javadoc, чтобы объяснить это.