Efficient way to search an element

Recently I had an interview, where they asked me a "searching" question.
The question was:

Assume there is an array of (positive) integers, of which each element is either +1 or -1 compared to its adjacent elements.

Example:

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

Now search for 7 and return its position.

I gave this answer:

Store the values in a temporary array, sort them, and then apply binary search.

If the element is found, return its position in the temporary array.
(If the number is occurring twice then return its first occurrence)

But, they didn't seem to be satisfied with this answer.

What is the right answer?

You can do a linear search with steps that are often greater than 1. The crucial observation is that if e.g. array[i] == 4 and 7 hasn't yet appeared then the next candidate for 7 is at index i+3. Use a while loop which repeatedly goes directly to the next viable candidate.

Here is an implementation, slightly generalized. It finds the first occurrence of k in the array (subject to the +=1 restriction) or -1 if it doesn't occur:

#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;
}

output:

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

Your approach is too complicated. You don't need to examine every array element. The first value is 4, so 7 is at least 7-4 elements away, and you can skip those.

#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;
}

Program output:

Steps 4, index 11

Edit: improved after comments from @Martin Zabel.

A variation of the conventional linear search could be a good way to go. Let us pick an element say array[i] = 2. Now, array[i + 1] will either be 1 or 3 (odd), array[i + 2] will be (positive integers only) 2 or 4 (even number).

On continuing like this, a pattern is observable - array[i + 2*n] will hold even numbers and so all these indices can be ignored.

Also, we can see that

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

so, index i + 5 should be checked next and a while loop can be used to determine the next index to check, depending on the value found at index i + 5.

While, this has complexity O(n) (linear time in terms of asymptotic complexity), it is better than a normal linear search in practical terms as all the indices are not visited.

Obviously, all this will be reversed if array[i] (our starting point) was odd.