CareerCup

bool findElement(int a[], int length, int expectedNum)
{
	int i = 0;
	while(i < length)
	{
		if(a[i] == expectedNum)
			return true;
		else
		{
			int diff = abs(expectedNum - a[i]);
			i = diff + i;
		}
	}
	return false;
}

Assume A[0]=m then
A[1]=m-1 or m+1
A[2]=m-2 , m, m+2
A[3]=m-3,m-1,m+1,m+3
So A[n] can be any one of these
A[n] = m-n, m-(n-2) , .......... , m+(n-2) , m+n
So A[i] belongs to m-i to m+i for i=1 to n
Hence we can perform a binary search at every level
Time:O(lg1)+O(lg2)+O(lg3)+....+O(lgn) = O(n) similar to construction of binary heap
if A[0]=m then the codemight look like this:

public static boolean bsearch(int start, int end, int ele) {
		int mid = start + (end - start) / 2;
		if (start > end)
			return false;
		if (ele == mid)
			return true;
		if (ele < mid)
			return bsearch(start, mid - 1, ele);
		else
			return bsearch(mid + 1, end, ele);
	}

	public static void main(String[] args) {
		int arr[] = {1,2,3,4,5,6,7,8,9,10,11,12,13};
		int m = arr[0];
		int k=12;
		for (int i = 1; i < arr.length; i++) {
			boolean found=bsearch(m-i,m+i,k);
			if(found)
			{
				System.out.println("index "+i+" = +k);
				System.exit(1);
			}
		}
		System.out.println("Not Found");
	}

If we follow A[i+1] = A[i]+1 OR A[i]-1 condition. So we can have an Array which have a least number and a greatest number and all the numbers in between two number.
Find the least one and greatest one and check for k. if least_num<= K <= greatest_num... then K is existing in Array of numbers.

For Example. {2, 3, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 8, 9}
so least_num = 2 and greatest_num=9. and you can have all the number in between 2 and 9
.... 2,3,4,5,6,7,8,9

now check for k(given number)....whether k is in between least_num and greatest_num.
No need to perform binary search and sorting here.
Order is O(n).

Correct me if I am wrong.

First, calculate the difference between k and value of first element. This will give the expected index of k (if k was there ). Then check the existence of the k at that index .If not found, then get the new value .Again get the new expected index by calculating difference between k and value at that index. Do it recursively. And yeah,some checks on these indexes is also needed.

Please post if there is any efficient method than this.

I think in this way:
Let ki=1 or -1
A[1]=A[0]+k1
....
A[j]=A[j-1]+kj=K
...

Then K=A[0]+k1+...Kj

Let x be the number of ki=1 and y be the number of ki=-1
Then
K-A[0]=x-y (1)
j=x+y (2)

Then the possible i s.t. A[i]=K can only appear in the solution of (1) and (2)

To make the above equations have a solution, we need

max{0, K-A[0]}<=j<=n-1, and j+K-A[0], j-(K-A[0]) are both even (i.e., j and abs(K-A[0]) the same odd or even)

Then we need check whether those A[j]=K

Is this idea ok?

It's not possible to do this faster than linear time in the most general case. Consider the sequence x, x-1,x, x-1, x, x-1, ..., x, x-1, x-2, x-1,x, x-1, x, ...

So all alternating x and x-1 except for that one x-2. Now ask whether the array contains x-2. Since it could validly be in the place of any x in this sequence, you won't know if it's there or not until you look at roughly n/2 entries.

That said, the parity of your target number will allow you to look at only the odd or only the even indexes, cutting running time in half. Note that each number has the opposite parity from its predecessor. Furthermore, if your target value is k and the current value you see is x, you can jump forward Math.abs(k-x) entries.

in A[n] , A[i+1] = A[i]+1 or A[i]-1
for that to happen , A[n] has to be continuos,
eg , if A[4+1] = 20 , then A[4] has to be either 19 or 21 .
and so on ..
if we have find the valve K =15,

Solution ,
go to A[n] , get the value if it <= 15 , then K is in A[],

public boolean isInArray(int[] arr, int value) {
 boolean result = false;
 int nextIdx = 0;
 
 while (nextIdx < arr.length && !result) {
  if (value == arr[nextIdx])
   result = true;
  nextIdx += Math.abs(value - arr[nextIdx]);
 }
 
 return result;
}

When the equation is done it is impossible to get a binary with the 2 last digits being 00 or 01. It took me a while to get to this. You can go through the logic on what will happen to the number of it is even or if it is odd.

public boolean isInArray(int value){
return ((value%4)==2 || (value%4)==3);
}

#include <iostream>
#include <stdio.h>
#define abs(a) (a)>=0?(a):-(a)

using namespace std;

int steps = 0;
int find(int a[], int n, int k) {
	int i = 0;
	while (i < n) {
		++steps;
		if (a[i] == k) {
			return i;
		}
		i += abs(a[i] - k);
	}
	return -1;
}

int main() {
	int a[]{2, 3, 4, 3, 2, 3, 4, 5, 6, 7, 8, 9, 8, 9};
	int n = sizeof(a)/sizeof(int);
	int k = 6;
	cout << find(a, n, k) << endl;
	cout << "Total steps :: " << steps << endl;
	return 0;
}

//The following function returns the index if the element is found otherwise -1

// Where a is the array, n is the number of elements and k is the required element.
int found( int a[], int n, int k) 
{
  int i = 0;
  if( k < ( a[0]-n+1 ) || k > ( a[0]+n-1) )
      return -1;
  while( i < n) {
       if( a[i] == k )
           return i;
       i =  i + ( ( a[i] > k ) ? ( a[i]-k ) : ( k-a[i] ) );
  }
}

int find_K(int array[],size n, int k)
{
int diff;
if( (k < a[0]-n-1) || ( k > a[0]+n-1) )
return 0; // not found
i=0;
while(i < n )
{
diff = (k < a[i] )? a[i]- k : k- a[i]);
if(diff==0)
return 1; // found
else
{
i+=diff;
}
}
return 0; // not found
}

The would be sorted in alternate fashion. So, it boils down to finding the element in each array using binary search.

I would look for the mininum and maximum, and if the number is between that range, is almost sure that the number is in the array. This would be the code in Java.

public static int[] findMinMax( int[] arr, int start, int end ){
    if( end - start + 1 == 1 ){	//an array part of length 1
	int[] minMax = { arr[ start ], arr[ start ] }; //end and strt are the same
	return minMax;
    }
    int mid = (end - start)/ 2;
    int[] mMLeft = findMinMax(arr, start, start + mid); //recursion on 1st half of arr[]
    int[] mMRight = findMinMax(arr, start + mid + 1, end); //recursion on 2nd half of arr[]
    int[] minMax = { Math.min( mMLeft[0], mMRight[0] ), Math.max( mMLeft[1], mMRight[1]) };	//find min and max of both left and right results
    return minMax;
}

public static Boolean containsSpecial( int[] arr, int k ){
	int[] minMax = findMinMax(arr, 0, arr.length-1);
	int min = minMax[0];
	int max = minMax[1];
	if( k > min && k < max ){
		return true;
        }
	return false;
}

if we check min and max one by one would take O(n), so is the same looking for the actual number, instead I split min and max problem in half and got a recursive solutions that solves the problem in O(log n) time, much more efficient in time (not so much in memory) for this problem.