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

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 
    }