搜索元素的有效方法

Question

最近我接受了采访,他们在那里问我一个" 搜索 "问题.
问题是:

假设有的(正)的整数,其中的每个元素是一个数组+1或-1比其相邻的元件.

例:

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

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

我给出了这个答案:

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

如果找到该元素,则返回其在临时数组中的位置.
(如果数字出现两次,则返回第一次出现)

但是,他们似乎并不满意这个答案.

什么是正确的答案？

Answer 1

您可以使用通常大于1的步骤进行线性搜索.关键的观察结果是,如果eg array[i] == 4和7尚未出现,那么7的下一个候选者就是索引i+3.使用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

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

编辑:经过@Raphael Miedl和@Martin Zabel的评论后改进.

Answer 3

传统线性搜索的变体可能是一个很好的方法.让我们选一个元素说array[i] = 2.现在,array[i + 1]将是1或3(奇数),array[i + 2]将是(仅正整数)2或4(偶数).

继续这样,一个模式是可观察的 - array[i + 2*n]将保持偶数,所以所有这些指数都可以忽略.

此外,我们可以看到

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

因此,i + 5应该接下来检查索引,并且可以使用while循环来确定要检查的下一个索引,具体取决于在index处找到的值i + 5.

虽然这具有复杂性O(n)(渐近复杂度方面的线性时间),但实际上它比普通线性搜索更好,因为没有访问所有索引.

显然,如果array[i](我们的起点)很奇怪,所有这些都将被颠倒过来.

Answer 4

John Coleman提出的方法很可能是面试官所希望的.
如果您愿意更复杂,可以增加预期的跳过长度:
调用目标值k.从位置p处的第一个元素的值v开始,并使用绝对值av调用差值kv dv.要加速负搜索,请查看最后一个元素作为位置o处的另一个值u:如果dv×du为负,则存在k(如果k的任何出现是可接受的,则可以在此处缩小索引范围二分搜索确实).如果av + au大于阵列的长度,则k不存在.(如果dv×du为零,则v或u等于k.) 省略索引有效性:探测序列可能返回v的("next")位置,其中k位于中间:. 如果dv×du为负,则从p + av到o-au找到k(递归地？); 如果它为零,则u等于o. 如果du等于dv并且中间的值不是k,或者au超过av, 或者你无法从p + av到o-au找到k, 那就让并继续探测. (对于'60年代文本的全面回放,请使用Courier查看.我的第一个第二个想法是"使用,这排除了du等于dv."
o = p + 2*av




p=o; dv=du; av=au;
o = p + 2*av - 1