该搜索算法的名称可能会产生误导,因为它的工作时间为 O(Log n)。该名称来自于它搜索元素的方式。
给定一个已排序的数组和要
搜索的元素 x,找到 x 在数组中的位置。
输入:arr[] = {10, 20, 40, 45, 55}
x = 45
输出:在索引 3 处找到元素
输入:arr[] = {10, 15, 25, 45, 55}
x = 15
输出:元素在索引 1 处找到
我们已经讨论过,线性搜索、二分搜索这个问题。
指数搜索涉及两个步骤:
1、查找元素存在的范围
2、在上面找到的范围内进行二分查找。
如何找到元素可能存在的范围?
这个想法是从子数组大小 1 开始,将其最后一个元素与 x 进行比较,然后尝试大小 2,然后是 4,依此类推,直到子数组的最后一个元素不大于。
一旦我们找到一个索引 i(在重复将 i 加倍之后),我们就知道该元素必须存在于 i/2 和 i 之间(为什么是 i/2?因为我们在之前的迭代中找不到更大的值)下面给出的是上述步骤的实施。
示例:
// C# program to find an element x in a
// sorted array using Exponential search.
using System;
class GFG {
// Returns position of first
// occurrence of x in array
static int exponentialSearch(int []arr,
int n, int x)
{
// If x is present at
// first location itself
if (arr[0] == x)
return 0;
// Find range for binary search
// by repeated doubling
int i = 1;
while (i < n && arr[i] <= x)
i = i * 2;
// Call binary search for
// the found range.
return binarySearch(arr, i/2,
Math.Min(i, n - 1), x);
}
// A recursive binary search
// function. It returns location
// of x in given array arr[l..r] is
// present, otherwise -1
static int binarySearch(int []arr, int l,
int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
// If the element is present
// at the middle itself
if (arr[mid] == x)
return mid;
// If element is smaller than
// mid, then it can only be
// present n left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only
// be present in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element
// is not present in array
return -1;
}
// Driver code
public static void Main()
{
int []arr = {2, 3, 4, 10, 40};
int n = arr.Length;
int x = 10;
int result = exponentialSearch(arr, n, x);
if (result == -1)
Console.Write("Element is not
present in array");
else
Console.Write("Element is
present at index "
+ result);
}
}
// This code is contributed by Smitha
输出
元素出现在索引 3 处
时间复杂度: O(Log n)
辅助空间:上述二分查找的实现是递归的,需要 O(Log n) 空间。通过迭代二分搜索,我们只需要 O(1) 空间。
指数搜索的应用:
1、指数二分搜索对于数组大小无限的无界搜索特别有用。请参阅无界二分搜索示例。
2、对于有界数组,以及当要搜索的元素更接近第一个元素时,它比二分搜索效果更好。