EMC Interview Question
Software Engineer / Developersmove 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)
but i think he wants the first occurrence of the number.
so i think we need to apply binary search to find the number and then move left or right to find the first occurrence.
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);
Given: array is of integers.
- newGeek June 03, 2008