搜索在数组中的重点，其中连续数相差+ 1 / -1 [英] Search for a Key in an Array in which consecutive numbers differ by +1/-1

问题描述

给定的一维数组。这个数组的每个数字由+1或-1不同于透水数量。示例：数组{5,6,7,6,5,6,7,8,9,8}

Given a one-dimensional array. Each number of this array differs from the pervious number by +1 or -1. Example: Array {5,6,7,6,5,6,7,8,9,8}

您将得到一个号码进行搜索的第一次出现在这个阵列（例如：搜索8 - 你的code应该回到7）。不要使用线性搜索。

You are given a number to search its first occurrence in this array (example: search for 8 -- Your code should return 7). Do not use Linear Search.

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

Without Linear Search, I could have tried it as follows:

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但别的东西，这种方法可以解决这个问题。

But this method is too generic. Even if the difference between the keys is NOT +-1 but something else, this method will solve this problem.

什么是如此特殊约±1的区别，它可以给我一个更好的解决方案？

What is so specific about +-1 difference, which can give me a better solution?

感谢。

推荐答案

假设你正在寻找16，和数组[0] = 8。这意味着你要搜索的数量可以阵列之前不会出现[ 8]，即（目标 - 阵列[0]）。所以，你读阵列[8]，其中有13个;这意味着目标不能阵列[11]前出现。等等。在+/- 1的区别，您可以提前在搜索中略过，因为你知道，如果数组[X] =（目标+/- N），目标数量不能阵列[X + N]之前出现。

Say you're searching for 16, and array[0] = 8. This means that the number you're searching for can't appear before array[8], i.e. (target - array[0]). So you read array[8], which has 13; that means that the target can't appear before array[11]. And so on. The +/- 1 difference lets you skip ahead in your search, because you know that if array[x] = (target +/- N) that the target number can't appear before array[x + N].

这篇关于搜索在数组中的重点，其中连续数相差+ 1 / -1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！