4

给定一个一维数组。该数组的每个数字与之前的数字相差 +1 或 -1。示例：数组 {5,6,7,6,5,6,7,8,9,8}

给你一个数字来搜索它在这个数组中的第一次出现（例如：搜索 8——你的代码应该返回 7）。不要使用线性搜索。

如果没有线性搜索，我可以尝试如下：

Check if (array[0] == Key)
{
        YES:
           return 0;
}

Take a variable: Diff = array[0]

// Keep on traversing the array, if Next Number>Current Number
   Diff += 1
   Else
   Diff -= 1

if (Diff==key)
{
    return current_index+1;
}

但是这种方法太笼统了。即使键之间的差异不是 +-1 而是其他的，这种方法也可以解决这个问题。

+-1 差异有什么特别之处，可以给我更好的解决方案？

谢谢。

4

3 回答 3

8

假设您正在搜索 16，并且 array[0] = 8。这意味着您要搜索的数字不能出现在 array[8] 之前，即 (target - array[0])。所以你读数组[8]，它有13；这意味着目标不能出现在数组[11]之前。等等。+/- 1 的差异使您可以在搜索中向前跳过，因为您知道如果 array[x] = (target +/- N) 目标编号不能出现在 array[x + N] 之前。

于 2013-05-12T03:29:45.873 回答
5

您无需查看列表中的每个数字。假设你正在寻找8，第一个数字是5。您可以安全地执行第 3 步，因为 8 不可能在少于三个步骤中发生。您可能会考虑稍微多一些 - 比如 6 - 因为可能有一些 -1，但我不知道这是否会更有效，因为您不确定它是“第一次”出现。所以让我们坚持原来的：

当您到达新数字时，您将确定下一步要采取的大小步骤 - 在上面，如果您采取了 3 步，您会找到 6，再走 2 (8-6)，然后再次找到 6，再走 2然后你发现 8 - 你在那里！你知道这是第一次出现，因为你跳过的数字不可能是 8。而且它只用了三步而不是七步。

于 2013-05-12T03:37:32.577 回答
5

选择的答案不是最优的。如果您试图最小化探针的数量（数组查找），您可以做得比从头开始搜索和采取的步骤小到`target - array[i]

由于您可以使用索引查找进行随机访问，因此您可以取得更大的进步。例如，如果您在以 开头的数组中查找9a[0] = 0，您可以检查a[16]它是否小于或等于0。如果没有，那么没有一个a[0 .. 16]可以达到9。

更大的步幅为您提供每个探针的更多信息（每个探针都可以让您排除左侧和右侧的指标）。与从左侧搜索时的最小步幅相比，这可以让您在每次探测时获得两倍的信息。

为了展示从中间搜索比从左搜索的优势，这里有一些用 Python 编程语言编写的工作代码：

def find(arr, value, bias=2):
    # With the bias at 2, new probes are in the middle of the range.
    # Increase the bias to force the search leftwards.
    # A very large bias does the same as searching from left side of the range.
    todo = [(0, len(arr)-1)]  # list of ranges where the value is possible
    while todo:
        low, high = todo.pop()
        if low == high:
            if arr[low] == value: return low
            else: continue
        mid = low + (high - low) // bias
        diff = abs(arr[mid] - value)
        if mid+diff <= high: todo.append([mid + diff, high])
        if mid-diff >= low: todo.append([low, mid - diff])
    raise ValueError('Value is not in the array')

从概念上讲，该算法正在做的是尝试通过每个探针获得尽可能多的信息。有时，它会很幸运并一次排除大范围；有时，它会很不幸，只能排除一个很小的子范围。不管运气如何，它的禁区将是从左搜索方法的两倍。

简单的测试代码：

arr = [10, 11, 12, 13, 14, 13, 12, 11, 10, 9, 8, 7, 6, 7, 8]
for i in range(min(arr), max(arr)+1):
    assert arr.index(i) == find(arr, i)
于 2013-05-12T04:02:12.370 回答