-2

有人有指数搜索的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);
4

2 回答 2

0

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

(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 是搜索键在数组中的索引。

于 2019-11-29T21:26:04.213 回答
-1

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

它大致遵循以下步骤：

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