例如,假设我想在文件中找到特定的单词或数字.内容按排序顺序(显然).由于我想在文件上运行二进制搜索,将整个文件复制到一个数组然后运行二进制搜索似乎真的浪费时间...我已经有效地将它变成了线性时间算法,因为我'在我运行搜索之前,我必须花费O(n)时间复制该darn文件.
有更快的方法吗？是否有类似lseek的东西可以使用行而不是字节？
如果没有,我最好只做一次线性搜索(假设我只在整个程序期间运行一次搜索)？
你不能直线寻求.一旦你想到这一点就很明显了.
但是你可以对文本文件进行一种二进制搜索.
你做的是:
基于磁盘的二进制搜索至少在开始时需要具有“ 块感知 ”能力，即，意识到以下事实：无论您读取一整串的单个字节，I / O成本都是相同的。另一个认为需要注意的是，与顺序读取操作相比，搜寻操作的成本相对较高。
它可以使用这种有关磁盘I / O特性的认识的几种方法：