algorithm - 未知大小数组的二进制搜索

标签 algorithm search binary-search

假设给定了一个数组并想在该数组中查找元素,您如何使用二进制搜索在该数组中搜索元素,并且给定的数组已经排序并且数组的大小未知。 可以应用线性搜索,但我正在尝试找出比线性算法更快的搜索。

最佳答案

如果你可以测试你是否落在数组范围之外,那么你可以使用修改后的二进制搜索(假设从 1 开始的数组):

  1. 下限 = 1,上限 = 1;
  2. while (A[upper] < element) upper *= 2;
  3. 正常二分搜索(下,上)。

否则,没有真正的方法可以做到这一点:假设您在某个地方找到了与您需要的元素相等的东西,您无法知道它是否已经从数组中掉落。

关于algorithm - 未知大小数组的二进制搜索,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16513429/

相关文章:

c++ - 在字符串列表中进行部分搜索

java - 如何在 map 中找到一个点并左右搜索

java - 线性搜索查找数组中目标的最后一个索引

c - C 中大磁盘文件的二进制搜索 - 问题

algorithm - 二分查找小于或等于查找值的最接近值

javascript - 注册检查电子邮件是否存在而不检查数据库

c++ - 寻找一组圆形数据的中位数

algorithm - 检查给定值 AorB 和 APlusB 是否存在 A 和 B

elasticsearch - ElasticSearch多词查询,匹配多个词比匹配几次但多次匹配更有值(value)

c++ - 有错误或不准确的二进制搜索