C++ 指数搜索算法

指数搜索是一种针对已排序数组的强大算法。它的效率来自于指数增长和二分搜索技术的战略性结合。该算法首先通过指数级递增的索引来扫描数组，直到找到目标值的可能位置。第一阶段就像在所有数组元素上撒下一张大网。

算法的这一部分指数级地加倍索引，直到它超出数组的边界，或者找到一个大于或等于目标的值。由于其广泛的覆盖能力，这种加倍的性质使算法能够处理未知大小或无界大小的数组。一旦确定了一个合适的范围，算法将进入下一阶段：在越来越窄的范围内进行二分搜索。

二分搜索以其在处理排序数组方面的高效率而闻名，它可以在给定范围内找到目标值的确切位置。二分搜索的本质是它精确地应用于指数增长期间确定的范围。该算法平衡了指数搜索和二分搜索方法的优势，以快速锁定目标值。

指数搜索比线性搜索或二分搜索算法具有更好的特性，尤其是在处理大型数据集或数组大小未知（无界）的情况下。该算法可以在合理范围内近似目标值的可能范围，并在必要时进行二分搜索。总而言之，指数搜索体现了通过智能探索来高效缩小搜索区域，然后在排序数组中快速而精确地发现所需目标值的理念。

方法一：递归指数搜索

递归指数搜索利用递归方法在排序数组中的指数之间进行遍历。这种迭代过程有助于快速定位可能找到目标值的范围。一旦确定了该范围，算法就会在该缩小的区间内进行二分搜索，以找到目标的精确位置。通过递归，它巧妙而简洁地遍历多个数组段，从而实现清晰易懂的实现。这种方法结合了指数增长和二分搜索的优点；因此，它成为解决在排序数组中定位目标值问题的强大解决方案。

程序

输出

Element found at index 6

说明

• binarySearch 函数
  排序后，在数组上执行此操作，并找到元素的位置。该函数的状态是它提供相关的数组（arr）以及紧邻的左值和右值（left 和 right）以及目标值（target）。
  该算法以循环方式执行，并将搜索空间分成两半，以便找到目标元素或耗尽所有空间。如果成功执行，它将打印找到值的索引；否则，它返回 -1。
• exponentialSearchRecursive 函数
  这里的可能性是指数搜索发生的递归状态。它暴露了（arr）、参数（target）的界限，以及（bound）限制了其参数列表的大小。这反过来又将区间分成两个不同的部分，并最终缩小了目标可以定位的结果范围。
  最终的算法在目标被发现时产生目标所在的位置索引；除此之外，算法会返回 -1。输出的结果限制值要么超出范围，要么低于初始值；它会一直返回 -1。
• exponentialSearch 函数
  此包装函数执行指数插值搜索，其中数组 arr 代表数据源，target 是其参数。它首先验证数组是否为空；否则，它返回 -1。
  它通过将索引加倍来搜索二分搜索的值范围，直到该索引处的值大于或等于目标。接下来，它通过指定的范围调用 binarySearch 函数，并最终相应地转发给定的结果。
• 主函数
  这是程序的第一步。该方法着手初始化排序数组样本（arr）和目标值（target），它应该搜索它。算法以指数搜索开始，并最终通过数组的后半部分验证结果。如果找到目标，它将打印其索引签名；否则，它将打印一条消息，说明元素未找到。程序运行后，计算机停止工作。

复杂度分析

时间复杂度

指数搜索（递归）

指数搜索的时间复杂度主要取决于两个因素

查找边界：如果将边界加倍所需的运算次数超过数组大小或目标值，算法性能会下降，边界增加的速度比必要的速度快。这些移动可能在O(log n)运行时完成，其中 'n' 代表数组的长度。

二分搜索：在指定初始范围后，进行二分搜索以查找确切位置。二分搜索的时间复杂度为 log n，其中范围大小为 n。

总体时间复杂度

考虑到最坏情况，即目标值位于数组末尾或不存在。在这种情况下，总时间复杂度相同，即O(log n)，其中 n 是数组的大小。

空间复杂度

确定递归指数搜索算法空间复杂度的特征是递归深度量与搜索要进行的步数之间的差异。

消耗的空间是额外的常量空间，用于在每次递归调用中维护参数和局部变量。

在递归指数搜索算法中，内存复杂度为 O(log n)，因为递归栈的高度最大。

方法二：迭代指数搜索

指数搜索算法采用迭代技术来探索排序数组中指数递增的值。它通过加倍索引来查找目标值可能存在的范围，直到该索引处的值大于或等于目标。然后反复应用二分搜索，将该范围缩小到越来越小的区间，直到找到正确的值。此方法不需要递归，适用于应排除递归开销以使实现高效但同时指数化的情况。

程序

输出

Element found at index 6

说明

• binarySearch 函数
  此方法具有在已排序数组中执行二分搜索的特定任务。数组的元素是左索引、右索引和目标值。
  它以迭代方式将搜索空间每次一分为二，直到找到目标值或搜索空间被耗尽。找到目标时，此函数返回索引；否则返回 -1。
• exponentialSearch 函数
  此方法负责指数搜索的迭代部分。它以数组和目标作为参数。该方法首先检查数组是否为空；如果为空，则返回 -1。
  接下来，它使用加倍索引的策略确定范围，直到索引值等于或大于目标。完成此操作后，它在数组的已识别部分调用 binarySearch 函数并返回结果。
• 主函数
  这些是此程序的第一步。它调用一个随机排序的数组 arr 和一个要查找的数字 target。它通过编写 exponentialSearch 函数来搜索数组的目标值。否则，数组会打印一条信息消息，说明元素不存在。程序执行完成后停止。

复杂度分析

时间复杂度

指数搜索（迭代）

迭代指数搜索的时间复杂度主要取决于两个因素

查找边界：在极端示例中，迭代的序列是 16、32、64……依此类推，并一直持续到它大于数组大小或接近目标。此任务需要O (log n)时间操作，其中 n 是数组的大小。

二分搜索：选定的范围成为二分搜索的区域。二分搜索的O(log n)复杂度，其中 'n' 是范围的大小。

总体时间复杂度

最坏情况发生在目标位于最后一个位置或不存在时，在这种情况下，时间复杂度将是O(log n)，其中 n 是数组的大小。

空间复杂度

迭代指数搜索算法所需的额外内存空间为O(1)，这意味着使用了恒定空间。此空间，始终位于前面，用于存储函数中的变量和参数。

操作不分配或释放内存块，它们没有递归；因此，无论输入数组的大小如何，空间复杂度都保持恒定。