CareerCup

Given: array is of integers.

This has been already discussed , we can do it with the help of Hash Map...with a complexity of o(1)

Hi,
can you please share link to the solution. I could not figure out o(1) solution. Are you sure about that? Isnt it o(log n)?

move in the step of power of ...
2,4,8, 16, 32,.. --> 2^i
moment u find a number less then or equal the required number stop.
if(num <= arr[2^i])
break
Apply binary search between the current index 2^i and 2^(i-1)

solution O(log n)

yeah ...the above solution is much better than hashing as hashing takes a preprocessing time of O(n) and space complexity of O(n) .

Why 2^i ? please explain.

We can directly apply binary search on this array because it is sorted.
Suppose an sorted array A[1..n].
In every step of binary search, we don't return if A[mid]==key.
Instead, we use this conditional statement:
if (key<=A[mid]) high=mid-1
else low=mid+1.
At last, we return value of low when low>high;
Time complexity is O(logN);