如何使用僅使用單詞而不使用數字的二進制搜索？

Question

我被要求使用二進制搜索到找到特定單詞在我們閱讀的文件中。

我不明白的問題是如何使用二進制搜索，當你正在尋找單詞而不是數字。

Answer 1

二進制搜索運行排序輸入。您也可以在單詞上定義order，而不僅限於值。例如，lexicographical order。在Java中，這甚至實現爲String的自然順序。所以你可以做"text1".compareTo("text2")，它會返回訂單。

---

二進制搜索的一個小例證：

正如你看到的，唯一在算法決定的，是兩個物體之間的順序。例如，從圖像中，7 < 14和7 > 6。如上所述，您也可以爲String s執行此操作。事實上，對於的所有內容，其中您的定義了訂單。

在Java中

其實很多類（超過150更多）實現自然秩序，它們在接口Comparable（documentation）中列出，它們都提供一個compareTo方法與有意義的順序。

Answer 2

想想在詞典中查找單詞;這是二進制搜索的一個例子。

例如，讓我們仰望「eunoia」：

1. 你翻開字典大約「E」部分，但也許你去得有點過分了和「M」部分中結束。
2. 你翻轉大約一半的路，現在你在「E」部分（如果你幸運的話）
3. 移到單詞中的下一個字母上並重復。

這一切工作，因爲字典是秩序井然，大家都一致認爲A是第一個字母，B是第二等的另一種方式來看待它是該字母是一樣的東西作爲不同名稱的數字[0 - 25]。

Answer 3

二進制搜索串實施了C.

char *lineptr[MAXLINE] //Array of char pointers stores the address of string 
    int binsrch(char srch[],int low,int high) 
    { 
     int mid; 

     if(high>=low){ 
      mid=(low+high)/2; 
      if(strcmp(srch,lineptr[mid])<0) //compare string stored in srch and lineptr[mid] 
       return binsrch(srch,low,mid-1,count); 
      else if(strncmp(srch,lineptr[mid],count)>0) 
       return binsrch(srch,mid+1,high,count);              
      else 
       return mid; // Found 
     } 
    return -1; //Not found 
    }