MediumNeetCode150ArrayBinary Search
Search in Rotated Sorted Array
Search for target in rotated sorted array.
Examples
Input
nums = [4,5,6,7,0,1,2], target = 0
Output
4
Found 0 at index 4.
Constraints
- •
1 <= nums.length <= 5000 - •
-10^4 <= nums[i] <= 10^4 - •
All unique - •
Rotated sorted
Approaches
O(n) scan.
CodeT: O(n) | S: O(1)
Find sorted half, search there.
CodeT: O(log n) | S: O(1)
def search(nums, target):
l,r=0,len(nums)-1
while l<=r:
m=(l+r)//2
if nums[m]==target: return m
if nums[l]<=nums[m]:
if nums[l]<=target<nums[m]: r=m-1
else: l=m+1
else:
if nums[m]<target<=nums[r]: l=m+1
else: r=m-1
return -1Same approach.
Diagram
One half is always sorted, check if target in that range
CodeT: O(log n) | S: O(1)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Linear Scan | O(n) | O(1) | O(n) scan. |
| Binary Search | O(log n) | O(1) | Find sorted half, search there. |
| Binary Search - Optimized | O(log n) | O(1) | Same approach. |
Linear Scan
T: O(n)S: O(1)
O(n) scan.
Binary Search
T: O(log n)S: O(1)
Find sorted half, search there.
Binary Search - Optimized
T: O(log n)S: O(1)
Same approach.
Common Mistakes
Not handling duplicates
Wrong sorted half detection
Off-by-one in bounds