遞歸二進制搜索Java

Question

我有一個名爲sArray的數組列表，它包含正確拼寫單詞的大量列表。我需要發送一個單詞到這個遞歸二進制搜索方法（鍵），並確定它是否拼寫正確。我理解遞歸二分法搜索是如何工作的，但我不確定如何確定是否需要左鍵或右鍵搜索與關鍵字相關的sArray，因爲我正在處理字符串而不是整數。

public int bSearch(String key, int lowIndex, int highIndex) { 

    if (lowIndex > highIndex) { 
     System.out.print("The word is incorrect"); 
     return -1; 
    } 

    mid = (lowIndex + highIndex)/2; 
    if (sArray.get(mid).equals(key)) { 
     return mid; 
    } else if (key < sArray.get(mid)) { 
     return bSearch(key, lowIndex, mid - 1); 
    } else { 
     return bSearch(key, mid + 1, highIndex); 
    } 
} 

Answer 1

CompareTo方法可以比較的是實現了Comparable接口的對象。由於String類實現了Comparable接口，因此compareTo將在您的方法中起作用。

一個方便的技巧，在使用的compareTo就像是減法思維它記住：

a.compareTo（二）將返回-1如果 - 否定的回答b。結果。 （a）在訂購它們之前出現b）

a.compareTo（b）如果a-b導致肯定答案，則返回1。 （訂購時他們談到b）後

a.compareTo（二）將返回0，如果一個 - B的結果爲0（有序當A和B是相同的）

所以......

if (key.compareTo(midValue) < 0) { 

     //look to the left of mid 
}... 

Answer 2

你可以很容易地比較字符串作爲整數：

if (testString.compareTo(key) < 0) { 
    ... 
} else if (testString.compareTo(key) > 0) { 
    ... 
} else { 
    ... 
}