Binäre Suche nach einem Array von Strings

Question

Ich frage mich, warum meine binäre Suche einen anderen Wert als meine lineare Suche zurückgibt. Kann mir jemand erklären, was ich falsch mache? Sollte ich etwas anderes zurückgeben?

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; 
} 

}

Hier ist, was es gibt. Die erste Gruppe ist mit der linearen Suche und die zweite mit der binären.

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

Versuchen Sie, Ihre Logik zu ändern:

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++ 
} 

Die lowIndex++ innerhalb des while war nicht erforderlich, da diese die lowIndex unabhängig von der BS zu aktualisieren war algorithn die Indizes auf dem Vergleich mit midIndex Wert basierend aktualisieren.