假设我们有 n 个单词和 n/k 个“页面”(假设 n/k 是一个自然数)。所以我们有一个“字典”，它实际上是一个“页面”数组，其中每个页面也是一个数组并且有 k 个单词。
单词的排序方式使得第 i 页中的所有单词在字典序上都小于第 i+1 页中的单词，但这些单词每个页面中的内容均未排序。
我需要编写一个在“词典”中查找特定单词的方法。我知道我应该使用二进制搜索来找到正确的页面，但我不太确定如何，因为每个页面中的单词都没有排序。
我错过了什么？
最佳答案
如果您不知道每个页面上排序的第一个/最后一个单词是什么，那么二分查找只能查找哪对页面可能包含该单词。
如果页面中的“顶部”单词出现在您想要的单词之前，那么您可以删除之前的所有页面，但不包括那个页面；在您的单词之后的页面下方可能还有另一个单词。
如果页面中的顶部词在您想要的词之后，那么您可以消除该词之后的所有页面，但不包括那个页面；页面下方可能有另一个词出现在您的词之前。
因此，当您完成二分查找时，您将剩下两页；第 N 页的首字小于您想要的字，第 N+1 页的首字大于您想要的字。
然后您必须在两个页面上进行线性搜索才能找到该词。
关于arrays - 二进制搜索 "dictionary"(二维数组)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27187929/