搜索在数组中的重点,其中连续数相差+ 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屋!