在C语言中运行二进制搜索的最快方法？

发布时间：2020-12-16 10:38:53 所属栏目：百科来源：网络整理

导读：例如,假设我想在文件中找到特定的单词或数字.内容按排序顺序(显然).由于我想在文件上运行二进制搜索,将整个文件复制到一个数组然后运行二进制搜索似乎真的浪费时间…我已经有效地将它变成了线性时间算法,因为我’在我运行搜索之前,我必须花费O(n)时间复制该d

例如,假设我想在文件中找到特定的单词或数字.内容按排序顺序(显然).由于我想在文件上运行二进制搜索,将整个文件复制到一个数组然后运行二进制搜索似乎真的浪费时间…我已经有效地将它变成了线性时间算法,因为我’在我运行搜索之前,我必须花费O(n)时间复制该darn文件.

有更快的方法吗？是否有类似lseek的东西可以使用行而不是字节？

如果没有,我最好只做一次线性搜索(假设我只在整个程序期间运行一次搜索)？

你不能直线寻求.一旦你想到这一点就很明显了.

但是你可以对文本文件进行一种二进制搜索.

你做的是：

>统计文件以获取长度或寻找结束并获得位置.>内存映射文件.(我认为这是最好的,但如果必须的话,你可以使用lseek并阅读.)>寻找文件的中间部分,减去平均线长.猜猜看.>向前扫描换行,除非您在0位置.>阅读你的专栏并进行比较.>重复1/4或3 / 4,1 / 8,1 / 16等.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!