指数搜索

Question

有人有指数搜索的Java实现吗？我找不到有关该算法的任何信息，也不知道如何实现它。像这样：

 * Signature method that must implement exponential search.
 * @ Param searchArray integer array in ascending.
 * @ Param x integer element to search for.
 * @ Return integer containing the position in the array <CODE> searchArray < CODE>
 * In case the element <CODE> x < CODE> be located in this otherwise
 * <CODE> Returns NOT_FOUND </ CODE>
public int exponentialSearch (int [] searchArray, int x);

Answer 1

如维基百科中所述，指数搜索算法假设列表已排序并包含两个阶段。

（1） 确定搜索关键字在哪个 （2^k-1， 2 k） 区间 （^k>=1）

（2） 在此区间内执行二叉搜索

整数数组中指数搜索的伪代码：

int exponentialSearch(int arr[], int size, int key)
{
    if (size == 0) {
        return NOT_FOUND;
    }
    int bound = 1;
    while (bound < size && arr[bound] < key) {
        bound *= 2;
    }
    return binarySearch(arr, key, bound/2, min(bound + 1, size));
}

该算法的复杂度为 O（log i），其中 i 是数组中搜索键的索引。

Answer 2

我敢打赌，这不是指数搜索，而是对二进制搜索的一种选择，其中您的数据已经按升序排序。

它大致遵循以下步骤：

• 您从一个定义为数组长度的下限除以 2 的点开始。
• 将点与要查找的值进行比较。
• 如果匹配，则返回找到它的位置。
• 如果较小，请将数组的子集从 0 到起点（不包括），然后重复上述步骤。
• 如果更大，请从起点 + 1 和数组的其余部分获取数组的子集，然后重复上述步骤。