7.7 Rotated Arrays
Standard binary search assumes the entire array is sorted.
7.7 Rotated Arrays
Standard binary search assumes the entire array is sorted. Rotated arrays violate that assumption while preserving enough structure to remain searchable in logarithmic time.
A rotated array begins as a sorted sequence and is then shifted around a pivot point. For example:
Original:
[1, 2, 3, 4, 5, 6, 7]
Rotated:
[5, 6, 7, 1, 2, 3, 4]
Although the array is no longer globally sorted, each half still contains useful ordering information. The challenge is determining which half remains sorted and whether the target can lie inside it.
This pattern appears in distributed systems, circular buffers, ring-based storage systems, time-series databases, and many interview problems because it requires reasoning about partial ordering rather than complete ordering.
Problem
Given a rotated sorted array and a target value, locate the target in logarithmic time.
Example:
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
Expected result:
4
A linear scan works:
func SearchLinear(nums []int, target int) int {
for i, v := range nums {
if v == target {
return i
}
}
return -1
}
However, the runtime is:
O(n)
We would prefer:
O(log n)
Understanding the Structure
Consider:
[4, 5, 6, 7, 0, 1, 2]
The array contains two sorted regions:
[4, 5, 6, 7]
[0, 1, 2]
The rotation creates a discontinuity.
The key observation is that at least one side of every midpoint remains sorted.
Suppose:
Index: 0 1 2 3 4 5 6
Value: 4 5 6 7 0 1 2
Midpoint:
v
[4, 5, 6, 7, 0, 1, 2]
The left half:
[4, 5, 6, 7]
is completely sorted.
This fact allows us to determine whether the target must lie on the left or right side.
Solution
At each iteration:
- Compute the midpoint.
- Determine which side is sorted.
- Decide whether the target belongs in that sorted region.
- Discard the impossible half.
func SearchRotated(nums []int, target int) int {
lo := 0
hi := len(nums) - 1
for lo <= hi {
mid := lo + (hi-lo)/2
if nums[mid] == target {
return mid
}
if nums[lo] <= nums[mid] {
if nums[lo] <= target &&
target < nums[mid] {
hi = mid - 1
} else {
lo = mid + 1
}
} else {
if nums[mid] < target &&
target <= nums[hi] {
lo = mid + 1
} else {
hi = mid - 1
}
}
}
return -1
}
Example:
nums := []int{4, 5, 6, 7, 0, 1, 2}
fmt.Println(SearchRotated(nums, 0))
Output:
4
Identifying the Sorted Half
The most important test is:
nums[lo] <= nums[mid]
If true:
[sorted][possibly rotated]
The left side is sorted.
Example:
[4, 5, 6, 7, 0, 1, 2]
^
^
lo mid
Values:
4 <= 7
Therefore:
[4, 5, 6, 7]
must be sorted.
If the condition is false, the right side must be sorted.
This follows from the fact that the array originated as a sorted sequence with a single rotation.
Deciding Which Half to Keep
Suppose:
[4, 5, 6, 7, 0, 1, 2]
Target:
5
The left half is sorted:
[4, 5, 6, 7]
Check:
nums[lo] <= target &&
target < nums[mid]
Result:
4 <= 5 < 7
True.
The target must lie inside the sorted left region.
Discard the right half.
If the target falls outside the sorted region, discard the sorted side and continue searching the other half.
This logic guarantees progress on every iteration.
Example Walkthrough
Search for:
target = 1
Array:
[4, 5, 6, 7, 0, 1, 2]
Initial state:
lo=0
hi=6
mid=3
value=7
Left side:
[4, 5, 6, 7]
is sorted.
Target:
1
does not belong to that range.
Discard the left side.
New interval:
[0, 1, 2]
Next midpoint:
1
Target found.
The search completes in logarithmic time.
Finding the Rotation Point
Sometimes the objective is not finding a target but finding the pivot itself.
Example:
[4, 5, 6, 7, 0, 1, 2]
The smallest element:
0
reveals the rotation point.
Observe:
[4, 5, 6, 7]
[0, 1, 2]
The minimum element is always located at the boundary between the two sorted regions.
Binary search can locate it efficiently.
func FindMin(nums []int) int {
lo := 0
hi := len(nums) - 1
for lo < hi {
mid := lo + (hi-lo)/2
if nums[mid] > nums[hi] {
lo = mid + 1
} else {
hi = mid
}
}
return nums[lo]
}
Example:
fmt.Println(
FindMin([]int{4, 5, 6, 7, 0, 1, 2}),
)
Output:
0
Why the Minimum Search Works
Consider:
[4, 5, 6, 7, 0, 1, 2]
Suppose:
mid = 6
hi = 2
Since:
6 > 2
the minimum must lie to the right.
The rotation point cannot exist inside a fully sorted region.
Conversely:
1 <= 2
indicates that the minimum may lie at the midpoint or to the left.
This gradually narrows the search interval until only the minimum remains.
Handling Duplicates
Duplicates complicate the structure.
Consider:
[2, 2, 2, 3, 4, 2]
The comparison:
nums[lo] <= nums[mid]
provides less information because equal values may appear on both sides.
One common approach is:
if nums[mid] == nums[hi] {
hi--
}
This shrinks the interval when ordering information is ambiguous.
However, the worst-case complexity can degrade to:
O(n)
when large blocks of duplicates exist.
Many practical implementations accept this trade-off.
Circular Buffer Perspective
Rotated arrays are common in systems programming.
Imagine a fixed-size ring buffer:
Capacity: 8
After enough insertions and removals:
[40, 50, 60, 70, 10, 20, 30]
The logical ordering remains intact, but the physical representation appears rotated.
Many circular data structures rely on reasoning similar to rotated-array binary search.
Complexity Analysis
Each iteration eliminates approximately half of the remaining search space.
Time complexity:
| Operation | Complexity |
|---|---|
| Search target | O(log n) |
| Find minimum | O(log n) |
| Extra memory | O(1) |
With duplicates:
| Operation | Worst Case |
|---|---|
| Search | O(n) |
because ambiguity may force gradual interval reduction.
Common Mistakes
A common error is assuming the left side is always sorted.
The correct approach is to test:
nums[lo] <= nums[mid]
during every iteration.
Another mistake is using ordinary binary search logic after identifying a sorted side. The target must first be checked against that side's boundaries.
A third mistake occurs when searching for the minimum. Comparing against nums[lo] often leads to more complicated logic. Comparing against nums[hi] generally produces a simpler invariant.
Finally, many implementations fail when the array contains a single element or is not rotated at all. Always verify these boundary cases.
Takeaway
Rotated arrays demonstrate that binary search does not require complete global ordering. A single rotation preserves enough structure for logarithmic search because at least one side of every midpoint remains sorted. By identifying the sorted region and determining whether the target can belong to it, the algorithm continues to eliminate half of the search space on every iteration. This technique generalizes to circular data structures, ring buffers, pivoted indexes, and many partially ordered search problems.