Microsoft Interview Question
Software Engineer / DevelopersTeam: MS Office Platform
Country: India
Interview Type: In-Person
int binary_serach(int* data, int size, int x) {
if (!data)
return -1;
int l = 0;
int r = size-1;
while (l<=r) {
int m = (l+r)/2;
if (data[m] == x)
return m;
if ((data[l] < data[m] && x>=data[l] && x<data[m]) ||
(data[l] > data[m] && (x>=data[l] || x<data[m])))
r=m-1;
else
l=m+1;
}
return -1;
}
why O(nlgn) ? if the array is sorted and rotated then use binary search to find the element in O(lgn) time.
- zahidbuet106 May 29, 2014