二進制搜索字符串數組

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裏面，因爲那是不考慮BS的更新lowIndex algorithn更新基於與midIndex值進行比較的指標是不是必需的。