- Forum
- General C++ Programming
- Quesstion
Quesstion
An element in a sorted array can be found in Big-O of logn times using binary search.But suppose I rotate the sorted array at some pivot unknown to you beforehand. So for instance 1,2,3,4,5 might become 3,4,5,1,2. Now devise a way to find an element in rotated array in Big-O logn times.
Can anyone hlp me in solving this question...?can anyone tell me that is it necessary to apply binary search in sorted arrays or not....
Can anyone hlp me in solving this question...?can anyone tell me that is it necessary to apply binary search in sorted arrays or not....
Use the same algorithm, but for the first recursion level add an offset of pivot+1. If the pivot cannot be know, then binary search cannot be used, since it doesn't work on unsorted arrays.
Note that you can't determine the pivot by linearly searching for the lowest value, as that takes O(n).
Note that you can't determine the pivot by linearly searching for the lowest value, as that takes O(n).
Topic archived. No new replies allowed.