Interview Question
Country: India
Interview Type: Written Test
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes
Search for the reset point [i.e., where the transition from high to low occurs ]. This can be done in O(log n);
Now, if the element that you need to search is
a.Greater than the value present at this location=>Doesnt exist;
b. Else, search a[o..this_index]..and a[ this_index+1...n-1];
O( log n ) on the whole for time complexity and O( 1 ) for space complexity.
*Any comments on this are most welcomed.
search for the mid from where the array is on the left of it decreasing and on right increasing
- DashDash May 15, 2012Can be done in O(n) time
Now take 3 pointers, low mid high and we can easily find the number using binary search