поиск в массиве, где элементы отличаются на 1

Question

Вопрос для интервью: задан массив, в котором любые два последовательных элемента отличаются по своим значениям на 1

пример:

vector<int> vec = { 1, 0, -1, -2, -3, -4,-3,-2,-1,0,1, 2, 1, 2, 3 };
            index==>0, 1,  2,  3,  4,  5, 6, 7, 8,9,10,11,12,13,14

Цель состоит в том, чтобы найти элемент K в этом массиве меньшечем O (N).

Моя попытка: начать с индекса 0.мы можем пропустить некоторые индексы.Поскольку элементы отличаются на 1, и нам нужно искать k, давайте посмотрим на элементы насекомых и увидим диапазон, между которым можно найти элемент.

index = 0

Максимальное значение, которое я могу предсказать, будет при [idx + k], а минимальное значение при [idx -k], так как каждое значение отличается на 1 ... однако, это ни к чему не приведет

РЕДАКТИРОВАТЬ: Код пытался предложить предложение в ответе

#include "stdafx.h"
#include "vector"
#include "iostream"
using namespace std;
int closeS(vector<int> & vec, int search , int& hopsTaken)
{
    int idx = 0;
    while (idx < vec.size() && vec[idx] != search)
    {
        idx += abs (search - vec[idx]);

        ++hopsTaken;
    }

    if (idx < vec.size())
    {
        cout << idx <<"\n";
        return idx;
    }

    return -1;
}

int main()
{
    int hopsTaken = 0;
    vector<int> vec = { 1,0,-1,-2,-3,-4,-3,-2,-1,0,1,2,1,2,3 };
    cout << closeS(vec, 3, hopsTaken);  // , 0, vec.size() - 1)];
    cout << "  \n hopsTaken " << hopsTaken <<"  in array size" << vec.size() <<" for k = " << 3 <<"\n";
    int y;
    cin >> y;

    return 0;
}

Попробовал несколько пунктов, и это всегда было <= O (n / k) </p>

Все еще в поисках лучшего, поскольку это все еще O (n)

Answer 1

Начните с первого индекса и перейдите по разнице к искомому элементу:

Например, поиск 2: начать с индекса 0

0, vec[0]=1,  2-1=1  => nextindex 0+1=1
1, vec[1]=0,  2-0=2  => 1+2=3
3, vec[3]=-2, 2--2=4 => 3+4=7
7, vec[7]=-2, 2--2=4 => 7+4=11
11, vec[11]=2

Например, поиск 3: начать с индекса 0

0, vec[0]=1,  3-1=2  => 0+2=2
2, vec[2]=-1, 3--1=4 => 2+4=6
6, vec[6]=-3, 3--3=6 => 6+6=12
12, vec[12]=1, 3-1=2  => 12+2=14
14, vec[11]=3