Search in a Rotated Sorted Array (O(log n) Binary Search)
Searching in a rotated array might look tricky at first — but with the right approach, it becomes elegant and efficient 🔥
Let’s break it down 👇
📌 Problem Statement
You are given a sorted array that has been rotated at some unknown index.
👉 Your task is to find the index of a target element.
⚠️ Constraints:
All elements are distinct
Must run in O(log n) time
If target not found → return -1
🧪 Examples
Example 1
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3
Input: nums = [1], target = 0
Output: -1
💡 Key Insight
Even though the array is rotated, one half is always sorted.
👉 At any point:
Either the left half is sorted
Or the right half is sorted
We use this property to apply Binary Search.
🧠 Algorithm Strategy
Find mid
Check which half is sorted:
If nums[low] <= nums[mid] → Left half is sorted
Else → Right half is sorted
Decide where target lies:
If target is in sorted half → search there
Else → search other half
🔄 Step-by-Step Logic
Case 1: Left Half is Sorted
nums[low] <= nums[mid]
If:
nums[low] <= target < nums[mid]
→ Search left
Else → Search right
Case 2: Right Half is Sorted
nums[mid] < nums[high]
If:
nums[mid] < target <= nums[high]
→ Search right
Else → Search left
💻 Python Implementation
def search(nums, target):
low, high = 0, len(nums) - 1
while low <= high:
mid = (low + high) // 2
if nums[mid] == target:
return mid
# Left half sorted
if nums[low] <= nums[mid]:
if nums[low] <= target < nums[mid]:
high = mid - 1
else:
low = mid + 1
# Right half sorted
else:
if nums[mid] < target <= nums[high]:
low = mid + 1
else:
high = mid - 1
return -1
Example usage
nums = [4,5,6,7,0,1,2]
target = 0
print(search(nums, target))
🧾 Output
4
🔍 Dry Run (Quick Insight)
For:
[4,5,6,7,0,1,2], target = 0
Mid = 7 → left sorted
Target not in left → move right
Eventually find 0 at index 4
⚡ Complexity Analysis
Metric Value
Time Complexity O(log n)
Space Complexity O(1)
Top comments (0)