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,

**Input: **

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

target = 10

**Output: **Element found at index 2

**Input: **

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.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include <iostream> using namespace std; // Function to find an element x in a circularly sorted array int CircularArraySearch(int A[], int n, int x) { // search space is A[low..high] int low = 0, high = n - 1; // iterate till search space contains at-least one element while (low <= high) { // find the mid value in the search space and // compares it with target value int mid = (low + high)/2; // if target is found, return its index if (x == A[mid]) return mid; // if right half (A[mid..high]) is sorted and mid is not // the target element if (A[mid] <= A[high]) { // compare target with A[mid] and A[high] to know // if it lies in A[mid..high] or not if (x > A[mid] && x <= A[high]) low = mid + 1; // go searching in right sorted half else high = mid - 1; // go searching left } // if left half (A[low..mid]) is sorted and mid is not // the target element else { // compare target with A[low] and A[mid] to know // if it lies in A[low..mid] or not if (x >= A[low] && x < A[mid]) high = mid - 1; // go searching in left sorted half else low = mid + 1; // go searching right } } // target not found or invalid input return -1; } // main function int main() { int A[] = {9, 10, 2, 5, 6, 8}; int n = sizeof(A)/sizeof(A[0]); int target = 5; int index = CircularArraySearch(A, n, target); if (index != -1) cout << "Element found at index " << index; else cout << "Element not found in the array"; return 0; } |

**Output: **

Element found at index 3

**Time complexity** of above solution is O(log(n)).

**Auxiliary space** used by the program is O(1).

**References:**

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂