你如何使用仅使用单词而不使用数字的二进制搜索？

Question

我被要求使用二进制搜索来查找特定的单词我们读了。

我不明白的问题是当您查找单词而不是数字时如何使用二分查找。

Answer 1

二进制搜索对排序的输入进行操作。您也可以在单词上定义 order，而不仅仅是在值上。

例如lexicographical order。在 Java 中，这甚至被实现为 String 的 自然顺序 。所以你可以做 "text1".compareTo("text2") 并且它 returns 订单。

二分查找小图解：

如您所见，算法中唯一要决定的是两个对象之间的顺序。例如，从图像中，7 < 14 和 7 > 6。如前所述，您也可以在 String 秒内执行此操作。事实上，对于您定义订单的所有东西。

实际上 Java 中的许多类（超过 150）实现了一个 自然顺序，它们列在接口 Comparable (documentation)，它们都提供了一个compareTo方法，具有有意义的顺序.

Answer 2

想到在字典里查一个词；这是一个二进制搜索的例子。

例如，让我们查找 "eunoia":

您将字典翻到大约 "E" 部分，但也许您走得太远了，最终进入了 "M" 部分。
你向后翻了大约一半，现在你在 "E" 部分（如果幸运的话）
移动到单词中的下一个字母并重复。

这一切都有效，因为字典有序，我们都同意 A 是第一个字母，B 是第二个字母，等等。另一种看待它的方式是字母表与数字 [0 - 25] 相同，只是名称不同。

Answer 3

二进制搜索 string 在 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
  }

你如何使用仅使用单词而不使用数字的二进制搜索？

How do you use a binary search using only words and not numbers?

java

binary-search