Microsoft Interview Question Solved

Microsoft Interview Question 0001

Given an array A[n] such that A[i+1] = A[i]+1 OR A[i]-1, and a number k, can you determine in most efficient way whether k is present in A[n] or not?

C implementation  of the solution 

Idea 1 : (Pure Linear Search)

bool find1(int a[], int k, int len){
 for( int i = 0; i < len; i++)
  if( a[i] == k)
   return true;
 return false;
}

Idea 2 :(Optimized)

bool find2(int a[], int k, int len){
 int i = 0;
 while(i < len){
  if(a[i] == k)return true;
  i += abs(k - a[i]);
 }
 return false;
}