CareerCup

Addition:
1 int array is sorted
2 the integer has duplicates

the question doesn't look like an "Amazon kinda question".
as the array is sorted all duplicates will be next to each other, so use the standard "Binary Search" itself, what's the issue with that. Efficiency = O(logn)

As you are required to find out only one match, the best way to do it is to check the first element(2^0), 2^1, 2^2....2^n,until you get one greater than desired. (I assume it is in increasing order)

Anonymous, that is a great idea. Or instead of exponential increase, we may use Fibonacci sequence instead.

Assume the element to be found is 'ElementToBeFound' and Array be 'A'
Start with index = 1, lastIndex = 0.

While( A[index] < ElementToBeFound )
{
lastIndex = index
index = index * 2
}
We have found the range where element could be found using reverse binary search
now use normal binary search to find element between A[lastIndex] and A[index]

Anonymous and Avinash, the time complexity of such an algorithm is
O(log n + log n/2 + ...)
=O(log^2 n)

@Avinash:
I agree that we need to have some way to make a good jump once we know the current element is less/equal/greater than the element we're looking for. But I'm not able to figure out what made you guys to think of the jump by doubling the index because the Q asks for Binary search?
As Hero already mentioned the complexity says the algo is pretty expensive, though the solution does work. Any other way of doing the same with more efficient solution?

jump further and further then retract

Suppose we have to find the element (integer), say i from the infinite array arr[].
In that case this is the pseudo-code of binary search that might work:
1. Jump to the ith location in the array
2. Let j = i
2. if (arr[j] > i) {
{low=j+1;}
{high=j+i;}
{j = j+i/2;}
} else {
{low=j-i;}
{high=j-1;}
{j = (j-i)/2;}
}
}

Can we use some random numbers for getting the pivot element ?