Binary Search on Rotated and Unsorted Arrays
Solve search-in-rotated-sorted-array and find-minimum-in-rotated-array by deciding which half is sorted at each step.
Binary Search on Rotated and Unsorted Arrays is a free DSA Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
What Is a Rotated Sorted Array?
A rotated sorted array is a sorted array that has been cut at some pivot and the two pieces swapped. For example, [4, 5, 6, 7, 0, 1, 2] is the sorted array [0,1,2,4,5,6,7] rotated at index 4. Standard binary search fails here because the array is no longer globally sorted.
The key insight is that at least one half of the array is always sorted after any rotation. Your binary search must identify which half is sorted before deciding where to move the boundaries.
# A rotated sorted array — one half is always sorted
arr = [4, 5, 6, 7, 0, 1, 2]
# Left half [4,5,6,7] is sorted
# Right half [0,1,2] is also sorted
# But left[0]=4 > right[-1]=2 => rotation happened in left-to-right crossingIdentifying the Sorted Half
After computing mid, compare arr[lo] with arr[mid]. If arr[lo] <= arr[mid], the left half is sorted; otherwise the right half is sorted. Once you know which half is sorted, you can check whether the target falls within that sorted range and narrow the search accordingly.
This decision tree lets you discard exactly half the array per step, preserving the O(log n) complexity even in a rotated array.
def search_rotated(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
# Left half is sorted
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
# Right half is sorted
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 0)) # 4
print(search_rotated([4, 5, 6, 7, 0, 1, 2], 3)) # -1Tracing Through an Example
Let us trace search_rotated([4,5,6,7,0,1,2], 0) step by step. Initially lo=0, hi=6, mid=3, arr[mid]=7. Is the target 0 in the sorted left half [4..7]? No, so we move lo=4. Now lo=4, hi=6, mid=5, arr[mid]=1. Left half [0,1] is sorted (arr[lo]=0 <= arr[mid]=1). Is 0 in [0..1)? Yes, so hi=4. Now lo=4, hi=4, mid=4, arr[4]=0 — found at index 4.
# Step-by-step trace
nums = [4, 5, 6, 7, 0, 1, 2]
target = 0
steps = []
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
steps.append(f'lo={lo} hi={hi} mid={mid} val={nums[mid]}')
if nums[mid] == target:
steps.append(f'Found at {mid}')
break
if nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
for s in steps:
print(s)Handling Duplicates in Rotation
When the rotated array may contain duplicates (e.g., [1,3,1,1,1]), the condition nums[lo] == nums[mid] is ambiguous — you cannot tell which half is sorted. The safe fix is to increment lo (or decrement hi) by one and retry. This degrades worst-case time to O(n), which you should mention to your interviewer.
def search_rotated_with_dups(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return True
# Ambiguous: shrink left boundary
if nums[lo] == nums[mid] == nums[hi]:
lo += 1
hi -= 1
elif nums[lo] <= nums[mid]:
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else:
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return False
print(search_rotated_with_dups([1, 3, 1, 1, 1], 3)) # True
print(search_rotated_with_dups([2, 2, 2, 0, 2], 0)) # TrueFind Minimum in Rotated Sorted Array
A related problem asks for the minimum element in a rotated sorted array without searching for a specific target. The minimum is always in the unsorted half. At each step: if arr[mid] > arr[hi], the minimum is in the right half (lo = mid + 1); otherwise it is in the left half including mid (hi = mid). When lo == hi, you have found the minimum.
def find_min(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # min is at mid or left of mid
return nums[lo]
print(find_min([3, 4, 5, 1, 2])) # 1
print(find_min([4, 5, 6, 7, 0, 1, 2])) # 0
print(find_min([11, 13, 15, 17])) # 11 (no rotation)Why arr[lo] <= arr[mid] Detects Sorted Left
The condition arr[lo] <= arr[mid] works because in a sorted (or sorted-with-no-rotation) segment the first element is always the smallest. If arr[lo] <= arr[mid], no rotation occurred within [lo..mid], so that half is sorted. The equality handles the case where lo == mid (a single-element segment is trivially sorted).
Conversely, if arr[lo] > arr[mid], the rotation pivot must lie between lo and mid, meaning the right half [mid..hi] is the contiguous sorted segment.
# Visualise: detect which half is sorted
examples = [
([4, 5, 6, 7, 0, 1, 2], 0, 6), # mid=3, val=7 => left sorted
([6, 7, 0, 1, 2, 4, 5], 0, 6), # mid=3, val=1 => right sorted
]
for arr, lo, hi in examples:
mid = lo + (hi - lo) // 2
if arr[lo] <= arr[mid]:
print(f'arr[{lo}]={arr[lo]} <= arr[{mid}]={arr[mid]} => LEFT half sorted')
else:
print(f'arr[{lo}]={arr[lo]} > arr[{mid}]={arr[mid]} => RIGHT half sorted')Complexity Analysis
Searching a rotated sorted array with binary search remains O(log n) time and O(1) space because we still halve the search space each iteration. The only difference from classic binary search is an additional constant-time check to identify which half is sorted.
With duplicates the worst-case degrades to O(n) because we may increment lo by only one at each step. Mention this trade-off explicitly — it shows you think about corner cases beyond the happy path.
LeetCode 33 Walk-Through
LeetCode 33 'Search in Rotated Sorted Array' is the canonical form of this problem. The constraints guarantee no duplicates and exactly one rotation. The solution is the search_rotated function we wrote earlier. Key interview points: always state the assumption of no duplicates, verify your inequalities with a concrete example at the boundary, and confirm the returned index is correct for both found and not-found cases.
# LeetCode 33 — complete solution
def search(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if nums[mid] == target:
return mid
if nums[lo] <= nums[mid]: # left half sorted
if nums[lo] <= target < nums[mid]:
hi = mid - 1
else:
lo = mid + 1
else: # right half sorted
if nums[mid] < target <= nums[hi]:
lo = mid + 1
else:
hi = mid - 1
return -1
# Tests
print(search([4,5,6,7,0,1,2], 0)) # 4
print(search([4,5,6,7,0,1,2], 3)) # -1
print(search([1], 0)) # -1LeetCode 153: Find Minimum No-Duplicate
LeetCode 153 'Find Minimum in Rotated Sorted Array' asks for the minimum without duplicates. The approach is to compare arr[mid] with arr[hi] (not arr[lo]) to determine which side the minimum is on. If arr[mid] > arr[hi] the minimum is to the right; otherwise it is at mid or to the left. This converges to the minimum in O(log n).
def findMin(nums):
lo, hi = 0, len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
return nums[lo]
print(findMin([3,4,5,1,2])) # 1
print(findMin([4,5,6,7,0,1,2])) # 0
print(findMin([11,13,15,17])) # 11Rotation Count and Pivot Index
Once you can find the minimum element, you also know the rotation count: the index of the minimum is exactly how many positions the array was rotated to the right. For example, in [4,5,6,7,0,1,2] the minimum is at index 4, so the array was rotated 4 positions.
Knowing the pivot lets you apply standard binary search by treating indices modulo n: real_idx = (mid + pivot) % n. This alternative formulation can simplify reasoning when working with circularly indexed structures.
def search_via_pivot(nums, target):
n = len(nums)
# Find pivot (index of minimum)
lo, hi = 0, n - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] > nums[hi]:
lo = mid + 1
else:
hi = mid
pivot = lo
# Binary search with offset
lo, hi = 0, n - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
real_mid = (mid + pivot) % n
if nums[real_mid] == target:
return real_mid
elif nums[real_mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1
print(search_via_pivot([4,5,6,7,0,1,2], 0)) # 4Putting It All Together
When you encounter a rotated array problem in an interview, follow this decision tree. First, determine whether you need to find a target or find the minimum. For finding a target use the sorted-half identification approach. For finding the minimum compare mid to hi. If duplicates are possible, mention the O(n) worst case and add the boundary-shrink fallback.
Practise by tracing your code on the three classic examples: no rotation, rotated once, and rotated to put the minimum at the last position.
Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: a rotated sorted array always has at least one sorted half, compare arr[lo] to arr[mid] to identify which half is sorted before deciding where to search, and finding the minimum uses arr[mid] vs arr[hi] to locate the rotation pivot. Next up we explore lower-bound and upper-bound binary search variants.
Frequently asked questions
Is the “Binary Search on Rotated and Unsorted Arrays” lesson free?
Yes — the full text of “Binary Search on Rotated and Unsorted Arrays” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Binary Search on Rotated and Unsorted Arrays”?
Solve search-in-rotated-sorted-array and find-minimum-in-rotated-array by deciding which half is sorted at each step. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Binary Search on Rotated and Unsorted Arrays” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Classic Binary Search: Left, Right, Mid
- Binary Search on Rotated and Unsorted Arrays
- Lower Bound and Upper Bound
- Answer-Space Binary Search