[解決済み] 要素検索の効率的な方法

質問

最近、面接を受けたのですが、そこで「quot」という質問をされました。 検索 という質問をされました。

という質問がありました。

正の）整数の配列があり、その各要素は以下のいずれかであるとする。 +1 または -1 は、その隣接する要素と比較して

例

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

ここで検索するのは 7 を検索し、その位置を返します。

こんな回答をしました。

値を一時配列に格納し、ソートしてからバイナリサーチをかけます。

要素が見つかったら、一時配列の中のその位置を返す。

(数字が2回出現している場合は、最初の出現位置を返す)

しかし、この答えには納得がいかなかったようです。

正しい答えは何ですか？

どのように解決するのですか？

1より大きいステップで線形探索を行うことができます。重要な観測は、例えば 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