指数搜索？

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

如Wikipedia中所述，指数搜索算法假定列表已排序，并且由两个阶段组成。

（（1）确定搜索关键字所在的（2 ^k-1，2 ^k）间隔（k> = 1）]

（（2）在此间隔内执行binary search

用于整数数组指数搜索的伪代码：

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

[我愿意打赌，这是对binary search的要求，而不是指数搜索，其中您的数据已经按照升序排序了。

大致遵循以下步骤：

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