Бинарный поиск - ошибка

Question

У меня есть список учеников, и я хотел бы отсортировать их по фамилии. Список студент выглядит как это:

Amanda 
Dorris 
Tucker 
Yasmin 
Zara 

Я хотел бы использовать бинарный поиск подход к поиску с помощью этих студентов и выхода желаемого результата.

Это то, что я до сих пор:

public void binarySearch(String keyword) { 

    int output; 

    if (fileSorted == false) { 
     System.out.println("The file " + fileName + " is not sorted. Please wait while it gets sorted..."); 
     bubbleSort(); 
     System.out.println("Thank you for your patience."); 
     System.out.println(); 
     System.out.print("Search for: "); 
     keyword = elmo.nextLine(); 
     output = doBinarySearch(keyword); 
    } else { 
     output = doBinarySearch(keyword); 
    } 
    System.out.println(output); 
} 

public int doBinarySearch(String keyword) { 

    int start = 0; 
    int end = numStudents - 1; 
    int mid; 
    int result; 

    while (start < end) { 
     mid = start + (end - start)/2; 
     result = students[mid].returnLastName().compareToIgnoreCase(keyword); 

     if (result == 0) { 
      return mid; 
     } else if ((end - start) <= 1) { 
      return -1; 
     } else if (result > 0) { 
      start = mid; 
     } else if (result < 0) { 
      end = mid; 
     } 
    } 
    return -1; 
} 

Answer 1

Линия

mid = ((end - start)/2); 

неправильно. Вам нужно установить mid на (примерно) серединой start и end, так

mid = start + (end - start)/2; 

или

mid = (end + start)/2; 

, если вы не боитесь переполнения.

С тем, что у вас есть, mid всегда находится в первой половине массива.

Кроме того, у вас есть случаи

} else if (result > 0) { 
     start = mid; 
    } else if (result < 0) { 
     end = mid; 
    } 

неправильно.

result = students[mid].returnLastName().compareToIgnoreCase(keyword); 

возвращает положительное число, когда фамилия students[mid] лексикографически больше keyword, так, то вам нужно изменить end, не start.

Answer 2

Вместо того, чтобы использовать неравенство в вашем состоянии контура - while (start != end) - использовать while (start < end). This is the typical approach. Когда вы проверяете на равенство, вы делаете предположение, что start и end изменяются только по одному на каждой итерации, и это необязательно может быть истинным.