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

Question

Мне интересно, почему мой бинарный поиск возвращает другое значение, чем мой линейный поиск. Может кто-нибудь объяснить мне, что я делаю неправильно? Должен ли я возвращать что-то другое?

public class BinarySearch extends SearchAlgorithm 
{ 
    public int search (String [] words, String wordToFind) throws ItemNotFoundException { 
    int lowIndex = 0; 
    int highIndex = words.length - 1; 
    while (lowIndex <= highIndex) { 
     int midIndex = (lowIndex + highIndex)/2; 
     if ((words[midIndex]).equals(wordToFind)) { 
      return midIndex; 
     } 
     if (wordToFind.compareTo(words[midIndex]) > 0) { //wordToFind > midIndex 
      lowIndex = midIndex + 1; 
     } 
     if (wordToFind.compareTo(words[midIndex]) < 0) { //wordToFind < midIndex 
      highIndex = midIndex - 1; 
     } 
     lowIndex++; 
    } 
    return -1; 
} 

}

Вот что он возвращается. Первая группа с линейным поиском, а вторая - с двоичным.

DISCIPLINES found at index: 11780 taking 0 comparisons. 
TRANSURANIUM found at index: 43920 taking 0 comparisons. 
HEURISTICALLY found at index: 18385 taking 0 comparisons. 
FOO found at index: -1 taking 0 comparisons. 

DISCIPLINES found at index: 11780 taking 0 comparisons. 
TRANSURANIUM found at index: 43920 taking 0 comparisons. 
HEURISTICALLY found at index: -1 taking 0 comparisons. 
FOO found at index: -1 taking 0 comparisons. 

Answer 1

Попробуйте изменить логику:

int midIndex = (lowIndex + highIndex)/2; 
while (lowIndex <= highIndex) {  
    if ((words[midIndex]).equals(wordToFind)) { //use equals 
     return midIndex; 
    } 
    if (wordToFind.compareTo(words[midIndex]) > 0) { //wordToFind > midIndex 
     lowIndex = midIndex + 1; 
    } 
    if (wordToFind.compareTo(words[midIndex]) < 0) { //wordToFind < midIndex 
     highIndex = midIndex - 1; 
    } 
// getting rid of infinite loop when the value is not in the list 
    if (lowIndex==highIndex && !wordToFind.compareTo(words[midIndex]) { 
     return -1; 
    } 
    midIndex = (lowIndex + highIndex)/2; // notice removing lowindex++ 
} 

lowIndex++ внутри while не требуется, так как это было обновление lowIndex независимо от БСА algorithn обновления индексов на основе сравнения со значением midIndex.