Efficient way to search an element

Question

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?

Answer 1

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