arrays - 在连续元素相差 +1/0/-1 的数组中有效地查找元素

Question

我有这个问题，我觉得我过于复杂了。我觉得这应该是非常基础的，但我遇到了一个心理障碍。

题目内容如下:

Given an array of integers A[1..n], such that A[1] ≤ A[n] and for all i, 1 ≤ i < n, we have |A[i] − A[i+ 1]| ≤ 1. Devise an semi-efficient algorithm (better in the worst case then the native case of looking at every cell in the array) to find any j such that A[j] = z for a given value of z, A[1] ≤ z ≤ A[n].

我对给定数组的理解如下:你有一个索引为 1 的数组，其中数组的第一个元素小于或等于数组的最后一个元素。数组的每个元素都在前一个元素的 1 中(因此 A[2] 可以是 A[1] 的值的 -1、0 或 +1)。

对于这个问题，我有几个解决方案，但都存在问题，这里举一个例子来展示我的思考过程。

i = 2
while i <= n {
    if (A[i] == x) then 
        break // This can be changed into a less messy case where
              // I don't use break, but this is a rough concept
    else if (abs(A[i] - j) <= 1) then 
        i--
    else 
        i += 2

}

然而，当数组中的大多数值重复时，这会失败。 [1 1 1 1 1 1 1 1 1 1 2] 的数组，例如搜索 2，它将永远运行。

我尝试的大多数算法都遵循递增 2 的类似概念，因为这似乎是处理最多递增 1 的数组时最合乎逻辑的方法，但是，我正在努力寻找任何可以在诸如 [1 1 1 1 1 1 1 1 1 1 2] 的情况下工作，因为它们要么失败，要么匹配 n 的 native 最坏情况。

我不确定我是否因为不明白问题在问什么而苦苦挣扎，或者我是否只是在努力拼凑一个算法。

符合要求的算法是什么样的？

Answer 1

这可以通过一种改进的二分查找形式来解决。最重要的前提:

• 输入数组总是包含元素
• 相邻元素之间的距离始终为1
• 总有一个包含搜索值的递增子数组

从那里我们可以应用两种策略:

• 分而治之:我们可以将搜索范围缩小一半，因为我们始终知道哪个子数组肯定会包含指定值作为递增序列的一部分。
• 限制搜索范围:假设搜索值为3，范围右半边的限制值为6，我们可以将右边界向左移动3个单元格。

作为代码(pythonesque，但未经测试):

def search_semi_binary(arr, val):
    low, up = 0, len(arr) - 1
    while low != up:
        # reduce search space
        low += abs(val - arr[low])
        up -= abs(val - arr[up])

        # binary search
        mid = (low + up) // 2

        if arr[mid] == val:
            return mid
        elif val < arr[mid]:
            # value is definitely in the lower part of the array
            up = mid - 1
        else:
            # value is definitely in the upper part of the array
            low = mid + 1

    return low

基本思想由两部分组成:
首先我们可以减少搜索空间。这利用了数组的相邻单元可能仅相差一个的事实。 IE。如果我们搜索空间的下界与 val 的绝对差为 3 ，我们可以将下限向右移动至少三，而不会将值移出搜索窗口。同样适用于上限。
下一步遵循使用以下循环不变式的二进制搜索的基本原理:
在每次迭代开始时，arr[low:up + 1] 中存在一个数组元素等于 val和 arr[low] <= val <= arr[up] .这在应用搜索空间缩减后也得到保证。取决于如何mid被选中，可能会发生以下三种情况之一:

• arr[mid] == val : 在这种情况下，找到搜索索引
• arr[mid] < val :在这种情况下arr[mid] < val <= arr[up]由于初始有效状态的假设，必须保持
• arr[mid] > val :类似于arr[mid] > val >= arr[low]

对于后两种情况，我们可以选择low = mid + 1 (或分别为 up = mid - 1)并开始下一次迭代。