Search an element in a circular sorted array

Given a circular sorted array of integers, search an element in it. Assume there are no duplicates in the array and the rotation is in anti-clockwise direction.


For example,

arr = [8, 9, 10, 2, 5, 6]
target = 10

Output: Element found at index 2

arr = [9, 10, 2, 5, 6, 8]
target = 5

Output: Element found at index 3

Related Posts: Find number of rotations in a circularly sorted array

A simple solution would be to run a linear search on the array and find the index of the given element. The problem with this approach is that its worst case time complexity is O(n). This solution also do not take advantage of the fact that the input is circularly sorted.

We can easily solve this problem in O(log(n)) time by modifying binary search algorithm. We know that the mid element always divides the array into two sub-arrays and target element can lie only in one of these sub-arrays. It is worth noticing that at-least one of these sub-arrays will always be sorted. If mid happens to be the point of rotation (minimum element), then both left and right sub-arrays will be sorted but but in any case one half (sub-array) must be sorted. We will make use of this property to discard left half or the right half at each iteration of the binary search.


Download   Run Code


Download   Run Code


Element found at index 3

Time complexity of above solution is O(log(n)).
Auxiliary space used by the program is O(1).


1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)


Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂

Leave a Reply

newest oldest most voted
Notify of

Looks like the Recursive call to function CircularArraySearch() is missing in the code


This is iterative code, not recursive one.