搜索元素的有效方法

Question

最近我接受了一次采访，他们问我一个“搜索”问题。问题是：

假设存在一个（正）整数数组，其中每个元素与其相邻元素相比要么是1，要么是-1。

例：

array = [4,5,6,5,4,3,2,3,4,5,6,7,8];

现在搜索7并返回其位置。

我给出了这样的答案：

将这些值存储在临时数组中，对它们进行排序，然后应用二进制搜索。

如果找到元素，则返回其在临时数组中的位置
（如果数字出现两次，则返回第一次出现的数字）

但是，他们似乎对这个答案不满意。

正确的答案是什么？

Answer 1

传统线性搜索的变体可能是一个很好的方法。让我们选择一个元素，比如数组[i]=2。现在，数组[i 1]将是1或3（奇数），数组[i 2]将是（仅限正整数）2或4（偶数）。

这样继续下去，一个模式是可观察的——数组[i2*n]将包含偶数，因此所有这些索引都可以忽略。

另外，我们可以看到

array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7

因此，接下来应该检查indexi 5，并且根据在indexi 5处找到的值，可以使用一个thon循环来确定要检查的下一个索引。

虽然这具有复杂性O（n）（渐进复杂性方面的线性时间），但在实际情况下，它比正常的线性搜索要好，因为所有索引都没有访问。

显然，如果数组[i]（我们的起点）是奇数，所有这些都将被逆转。

Answer 2

你的方法太复杂了。不需要检查每个数组元素。第一个值是4，因此7至少是7-4元素，您可以跳过这些元素。

#include <stdio.h>
#include <stdlib.h>

int main (void)
{
    int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
    int len = sizeof array / sizeof array[0];
    int i = 0;
    int steps = 0;
    while (i < len && array[i] != 7) {
        i += abs(7 - array[i]);
        steps++;
    }
    
    printf("Steps %d, index %d\n", steps, i);
    return 0;
}

程序输出：

Steps 4, index 11

编辑：在@Martin Zabel的评论之后有所改进。

Answer 3

可以使用通常大于1的步长进行线性搜索。关键的观察结果是，如果例如数组[i]==4而7尚未出现，那么7的下一个候选者位于索引i3。使用一个while循环，它会反复直接指向下一个可行的候选人。

下面是一个实现，稍微概括一下。它查找数组中第一次出现的k（受=1限制）或-1如果没有出现：

#include <stdio.h>
#include <stdlib.h>

int first_occurence(int k, int array[], int n);

int main(void){
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
    printf("7 first occurs at index %d\n",first_occurence(7,a,15));
    printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15));
    return 0;
}

int first_occurence(int k, int array[], int n){
    int i = 0;
    while(i < n){
        if(array[i] == k) return i;
        i += abs(k-array[i]);
    }
    return -1;
}

输出：

7 first occurs at index 11
but 9 first "occurs" at index -1