CareerCup

variation of binary search i.e.. reverse binary search.
check the target number is present in below index ranges i.e.. 2^n index range
0-1
2-3
4-7
8-15
16-31
32-63
.
.

if target number is found in any of the above range then apply binary search on data in that range

int start=0, end = 1;
int i = 1;    // to apply binary search from intermediate data
if target <= a[end]
   apply binary search for the range start and end
else
   i *= 2;
   start += i;
   end += i;
   if arr[start] == '$'
      print(data not found)
      break
   else if arr[end] == '$' // start is number and end is '$' then apply BS from start
       i = 1
       end = start + 1

time complexity is O(log n)

The following is a solution in Java. Assumes that sorted integers are unique. We start by looking at position k since we're guaranteed that the value won't be in a position greater than k. Once we've checked k, we can then do a binary search on the range 0..k-1. This solution is O(log k).

public static int findPosition(String[] input, int k) {
	if (input == null || input.length == 0 || input[0] == "$")
		return -1;
	if (input[k] == Integer.toString(k))
		return k;
	return binarySearch(input, k, 0, k-1);
}

public static int binarySearch(String[] input, int k, int start, int end) {
	if (end < start)
		return -1;
	int mid = (start + end) / 2;
	// Convert string array value to int, if possible
	int midValue = -1;
	if (input[mid] != "$")
		midValue = Integer.parseInt(input[mid]);
	// Check mid point
	if (midValue == k)
		return mid;
	// Search low if mid value is greater than k
	// or if it is "$"
	if (midValue > k || input[mid] == "$")
		return binarySearch(input, k, start, mid - 1);
	// If mid point isn't "$", then search the upper range
	else if (input[mid] != "$")
		return binarySearch(input, k, mid + 1, end);
	return -1;
}

Since the target is an infinite array, we are guaranteed not to reach its end (presumably)! We can start by searching every 2^k, k=0,1,... (i.e., arr[(1<<k)-1]) location (hence, o(lg n)) until we
1.either hit the value we are looking for so return the (1<<K)-1 as its location
2. we hit a value greater than the value we are looking for OR a '$'

If the second case occurs, then we know our value should be somewhere between indices 0 and (1<<k)-1. Do a binary search within this limit until you either find the value or figure out no such value exists.

Simply find the value "n" in O(logn) time and then apply binary search.
The value "n" can be found out as follows:
i=1;
while(arr[i]!='$')
i*=2;
n=i;

bool searchInfiniteArray(int[] a)
{
bool lastBlock = false;
for (int k=0; ; k++);
{
int lo(1 << k - 1), hi(1 << (k+1) - 1), x;
while (lo <= hi)
{
x = lo + (hi-lo)/2;
try {
if (a[x] == target) return x;
else if (a[x] > target) return hi = x-1;
else lo = x+1;
}
catch(Exception e) { hi = x-1; lastBlock = true; }
}
if (lastBlock) return false;
}
}

First question to interviewer should be, how can arrays contain combination of int and Strin/Char values? Arrays are strongly typed.

Assuming all integers are unique... we have to find a

right = -1;
loop:
Let left = right + 1;
step: Let diff = a - arr[left];
if diff < 0
    	if left == 0
		a is not in the array;
    	else
		a will be into 0 to left - 1; use binarysearch(arr[], 0, left - 1, a);
else
right = left + diff;
goto loop: