#coding interview question

Given an unsorted array in which every adjacent element is differ by either +1 or -1

Write an efficient code to find x where x is also given.

Solution 1:

Binary Chop the elements till we encounter either x-1, x, or x+1 then search nearby for x.

Solution 2:

(approach when many x are involved)

Perform an insertion sort followed by a binary search.

Insertion sort is usually O(n^2) but in this case the positions are off by +-1 so we have to look at cells that either contain x-1, x, x+1 and how many ever duplicates there may be.

void InsertionSort(int A[], int length, int x){

for (int i =0; i < length; i++){

int j = i;

while (j > 0 && A[j-1] > A[j]){

      // Swap(A[j],A[j-1]);
      int temp = A[j];
      A[j] = A[j-1];
      A[j-1] = temp;

       j = j - 1;

}

}

int Search(int A[]. int length, int x){

InsertionnSort(A, length, x);
return exists(A, length, x, 0, length-1);
}