通常在排序集中搜索时，二分搜索是一种快速、美观且简单的数据定位方法。然而，它确实在具有一组任意大但未知大小的假设场景中崩溃，因为它不能将其上限设置为无穷大。
为了解决这个问题，可以想象做一个，因为没有更好的术语，“反向二分搜索”来找到粗略的下限/上限，然后执行一个常规的二分查找：
min = 0
max = 1
while( set[max] exists && set[max] < target ) {
min = max + 1
max *= 2
}
binarySearch(min, max)
由于这似乎是一个微不足道的算法，我不可能是第一个想到它的人，所以我的问题只是这个算法是否有名字（如果有，它是什么）。
这似乎被称为指数搜索、加倍搜索或疾驰搜索。我也听说过它称为几何扩展搜索或类似的东西。原则上，它类似于计算机编程中经常用于调整动态数组大小的几何扩展策略。以这种方式调整动态数组的大小可确保添加元素需要时间。这不一定依赖于每次将存储量翻倍，您可以使用 3 或 3/2 或任何其他大于 1 的数字。
如果您使用此方法查找区间的上限，然后使用二进制搜索查找您需要的确切元素对于算法的每个部分，其中 N 是最终找到的条目的索引。对许多搜索进行平均，如果您需要找到条目的概率，我认为这将是一个最佳搜索策略正比于. 换句话说，如果您希望优先选择靠近数组开头的点，这将是一个很好的策略。
在连续设置中，如果您试图找到函数达到某个值的位置并且您所知道的只是该函数近似呈指数增长，这将很有用。您可以使用二进制扩展搜索来查找包含所需值的范围，然后使用二进制搜索来缩小精确值。当然，在这种情况下有更快的搜索方法（更好地利用您对函数的了解或使用更高阶的搜索方法），特别是对于表现良好的函数，但这可以让您以非常简单的方法获得合理的效率。