Seaching for an element in a circular sorted array
- by guirgis
I wanted to share this with you, i had this problem in a google interview. we want to search for a given element in a circular sorted array in complexity not greater than O(Log n).
ex: search for 13 in {5,9,13,1,3}.
My idea was to convert the circular array into a regular sorted array then do a binary search on the resulting array, but my problem was the algorithm i came up was stupid that it takes O(n) in the worst case:
for(i = 1; i < a.length; i++){
if (a[i] < a[i-1]){
minIndex = i; break;
}
}
then the corresponding index of ith element will be determined from the following relation:
(i + minInex - 1) % a.length
it is clear that my conversion (from circular to regular) algorithm may take O(n), so we need a better one, any suggestions?
