LeetCode 33 · Binary Search · concept: modified-binary-search
Problem
Search for target in a rotated sorted array of distinct values. O(log n).
[4,5,6,7,0,1,2], target = 0 -> 4
[4,5,6,7,0,1,2], target = 3 -> -1
The idea — find the sorted half, then bound the target
At each step one half [l,mid] or [mid,r] is fully sorted (building on Find Minimum). Identify it, then check whether target lies within that sorted half’s value range: if yes, search there; if no, search the other half.
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2
if nums[mid] == target:
return mid
if nums[l] <= nums[mid]: # left half [l..mid] is sorted
if nums[l] <= target < nums[mid]:
r = mid - 1 # target within the sorted left
else:
l = mid + 1
else: # right half [mid..r] is sorted
if nums[mid] < target <= nums[r]:
l = mid + 1 # target within the sorted right
else:
r = mid - 1
return -1Time O(log n), space O(1).
The reasoning
You can only reason about a range whose endpoints you trust — and the sorted half is exactly that. Once you know, say, the left half spans [nums[l], nums[mid]] in sorted order, a simple range check tells you whether target is inside it. The rotation is handled entirely by first asking “which half is the clean, sorted one?”
Key insight
Rotated search = (identify the sorted half) + (range-check the target against it). It composes plainly with the previous problem: the same “one half is always sorted” fact, now used to place a specific value rather than find the pivot.
Related
- concept: modified-binary-search
- builds on: Find Minimum in Rotated Sorted Array
- prev: Find Minimum · next: Time Based Key-Value Store
Software engineering
Infrastructure & security
Computer science
Hardware & engineering