Introduction

A circular sorted array is usually just a sorted array rotated around some pivot. You can still search it in logarithmic time, but the binary search logic must account for the fact that only one half of the current range is guaranteed to be normally sorted.

What Makes The Array "Circular"

Take a sorted array such as 2, 4, 6, 8, 10, 12. If you rotate it after 8, the result becomes 10, 12, 2, 4, 6, 8. The data is no longer globally sorted from left to right, but every search interval still contains one half that is sorted.

That property is the key insight. On each step:

1. compute the middle index
2. check whether the left half is sorted
3. if not, the right half must be sorted
4. decide whether the target lies inside the sorted half
5. discard the other half

This keeps the time complexity at O(log n) as long as the values are distinct.

Binary Search On A Rotated Array

Here is a Python implementation that returns the index of the target or -1 if the value is missing.

1def search_rotated(nums, target):
2    left = 0
3    right = len(nums) - 1
4
5    while left <= right:
6        mid = left + (right - left) // 2
7
8        if nums[mid] == target:
9            return mid
10
11        if nums[left] <= nums[mid]:
12            if nums[left] <= target < nums[mid]:
13                right = mid - 1
14            else:
15                left = mid + 1
16        else:
17            if nums[mid] < target <= nums[right]:
18                left = mid + 1
19            else:
20                right = mid - 1
21
22    return -1
23
24
25values = [10, 12, 15, 1, 3, 6, 8]
26print(search_rotated(values, 3))
27print(search_rotated(values, 11))

The test nums[left] <= nums[mid] tells you whether the left half is in normal sorted order. If it is, you can check whether the target falls inside that range. Otherwise, the right half must be the sorted one.

Step-By-Step Example

Suppose the array is 13, 18, 25, 2, 8, 10 and the target is 8.

• 'left = 0, right = 5, mid = 2, value is 25'
• the left half 13, 18, 25 is sorted
• '8 is not in that range, so move to the right half'
• now left = 3, right = 5, mid = 4, value is 8
• match found at index 4

The algorithm never needs to explicitly find the rotation pivot first. It discovers enough structure during search to eliminate half the range on each iteration.

Alternative Two-Step Approach

Another valid solution is:

1. find the pivot index, which is the smallest value
2. run ordinary binary search on the correct side of the pivot

That is still O(log n), but it is more code and usually not necessary unless you also need the pivot for other operations.

Here is a compact pivot finder:

1def find_pivot(nums):
2    left = 0
3    right = len(nums) - 1
4
5    while left < right:
6        mid = left + (right - left) // 2
7        if nums[mid] > nums[right]:
8            left = mid + 1
9        else:
10            right = mid
11
12    return left
13
14
15print(find_pivot([10, 12, 15, 1, 3, 6, 8]))

Use this version if the broader problem asks for both search and rotation analysis.

What About Duplicates

Duplicates make the problem less clean. If nums[left] == nums[mid] == nums[right], you cannot always tell which side is sorted. In that case, a common fallback is to shrink both ends by one and continue.

That works, but it can degrade to O(n) in the worst case. If the interview or problem statement assumes distinct values, the earlier logarithmic algorithm is the intended answer.

Common Pitfalls

The most common bug is using normal binary search assumptions on the entire array. A rotated array is not globally sorted, so comparing only with nums[mid] is not enough.

Another frequent mistake is using the wrong inequality boundaries. For example, if you write target <= nums[mid] in the left-half test after already checking nums[mid] == target, you can accidentally keep the middle element in the search range and create an infinite loop.

Duplicates are another trap. The clean O(log n) logic assumes distinct elements. If duplicates are allowed, add an explicit case for ambiguous boundaries.

Finally, remember that the array is not truly circular in memory. It is just a rotated sorted array stored linearly. Thinking about it that way makes the index logic much easier to reason about.

Summary

• A circular sorted array is usually a rotated sorted array.
• You can search it in O(log n) by identifying which half of the current interval is sorted.
• The one-pass binary search is simpler than first finding the pivot in most cases.
• Duplicates complicate the sorted-half check and can degrade performance.
• Careful boundary conditions are the difference between a correct logarithmic search and an infinite loop.