在数组中搜索连续数字相差+ 1/-1的键

Question

给定一维数组.该数组的每个数字与前一个数字相差+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差异有什么特别之处,这可以给我一个更好的解决方案？

谢谢.

Answer 1

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

Answer 2

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

当你到达新的号码时,你确定下一步要采取的步数 - 在上面你已经采取了3步,你会找到6,再步2(8-6),你再找到6,再步2你找到8 - 你在那里!你知道这是第一次出现,因为你跳过的数字不可能是8.而且只需要三步而不是七步.

Answer 3

所选答案不是最佳的.如果您正在尝试最小化探测器的数量(阵列查找),那么您可以做得比从头开始搜索更好,并采取尽可能小的步骤`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)