Java - binarySearch（）。如何爲拼寫檢查設置二進制搜索

Question

我正在執行拼寫檢查項目。我有一個單詞列表，然後葛底斯堡的地址，有些單詞拼寫錯誤。我的工作是確定哪些單詞拼寫錯誤，然後在打印出地址時在拼寫錯誤的單詞下打印出星號或其他內容。我的問題是在binarySearch部分。我不確定的語法和javadoc看起來像它的中文。這裏是我的源代碼（binarySearch朝向底部）

/* 
* Assignment 1: Spell Check 
* Professor Subrina Thompson 
* CS102 
*/ 
package spellcheck; 

import java.util.*; 
import java.io.*; 

public class SpellCheck { 

    //48,219 words in the words.txt 

    //Declare Variables 
    static FileReader reader; 
    static Scanner input; 
    static ArrayList <String> wordList = new ArrayList<String>(); 
    static FileReader reader2; 
    static Scanner input2; 
    static String testWord; 
    static String index; 

    //Main Method 
    public static void main(String[] args) throws FileNotFoundException { 
     fileSort(); 
    } 

    //Open file to be read from 
    public static void openFile() throws FileNotFoundException { 
     reader = new FileReader("words.txt"); 
     input = new Scanner(reader); 

    } 

    //sort the file 
    public static void fileSort() throws FileNotFoundException{ 
     openFile(); 

     //read the word list into an ArrayList 
     while (input.hasNext()){ 
      wordList.add(input.next()); 
     } 

     //Sort the array 
     Collections.sort(wordList); 
    } 

    //read the gettysburg address 
    public static void gAddress()throws FileNotFoundException{ 
     reader2 = new FileReader("gettysburg.txt"); 
     input2 = new Scanner(reader2); 

     //create loop to place word from file into a var then test to see if it is in the dictionary 
     for(int i = 0; i < wordList.size(); i++){ 

      //place the word into a variable 
      testWord = input2.next(); 

      //test if the word is in the dictionary 
      index = Collections.binarySearch(wordList,testWord); 
     } 
    } 

    //compare the address and array through binary search 

    //print out if spelling is correct 
} 

PS。我知道它並不完整，而且有很多鬆散的結局，但它仍然是一項進展中的工作。

編輯：

我試圖使基於關閉的binarySearch如何我明白工作的一個新的搜索功能。這是該函數的代碼。在 「列W」 將是字典中的單詞，從地址檢測對testWord：

公共靜態INT的binarySearch（列W）{

 int start = 0; 
     int stop = wordList.size() - 1; 

     while (start != stop){ 
      int half = ((stop - start)/2) + start; 
      int res = wordList.get(half).compareToIgnoreCase(w); 

      if(res == 0){ 
       return half; 
      } 
     else if(stop - start <= 1){ 
       return -1; 
      } 
     else if(res > 0){ 
       start = half; 
      } 
     else if(res < 0){ 
       stop = half; 
      } 


    } 

    return -1; 
} 

Answer 1

這就是你需要：

if(index < 0) { 
    System.out.println(testWord + " not in dictionary"); 
} 

此外，通過檢查index的絕對值，您可以輕鬆地找到字典中按字母順序與錯誤輸入的單詞相近的單詞。

Answer 2

創建循環來把文件從字到一個變量，然後進行測試，看看它在字典中

但是，這不是你在做什麼。您正在創建一個循環來檢查字典中的所有單詞，並檢查地址中的下一個單詞是否在字典中，並且無論它是否被發現都無所事事。

如果詞典有更多的單詞，那麼解決您的問題可能會得到例外，如果地址有更多的單詞，那麼您將不會檢查所有單詞。

Answer 3

javadoc看起來像中文導致列表是通用的。

public static <T> int binarySearch(List<? extends Comparable<? super T>> list, T key) 

應該用T作爲任何泛型類型來讀取，T是鍵的類型。 第一個參數列表必須是實現T派生類型的Comparable接口的類型的列表。

在你的情況下，密鑰類型T是String。這是一個字符串列表。 String實現Comparable，String是String的超類。所以這是有效的。

如果您在串補，方法的簽名變成了更多的東西正常：

public static int binarySearch(List<String> list, String key) 

因此，因此，給予

int index; 
List<String> list; 
String key; 

調用看起來像

index = Collections.binarySearch(list, key); 

之後index將包含列表中的搜索關鍵字的索引或負值如果沒有找到密鑰，則爲數字。更確切地說：

搜索關鍵字的索引，如果它包含在列表中;否則， （ - （插入點） - 1）。插入點被定義爲鍵將被插入列表中的點 ：如果 列表中的所有元素都小於第一個元素的索引（大於鍵或012），則返回list.size（）指定的鍵。請注意，這保證 當且僅當找到密鑰時，返回值將>> 0。