Binary Search
LeetCode 704 • Easy • Arrays
Input: nums = [-1, 0, 3, 5, 9, 12], target = 9 → Output: 4
Find target in sorted array. Return index or -1 if not found.
TimeO(log n)halve each step
SpaceO(1)pointers only
Left: —
Right: —
Mid: —
Ready
Press Play. Binary search: left, right, mid. Halve search space each step. O(log n).
TimeO(log n)halve each step
SpaceO(log n)call stack depth
3
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
PATTERN ▸ left, right, mid; halve search space O(log n) · O(1)
① INIT
left, right = 0, len(nums)-1
② LOOP
while left <= right:
③ MID
mid = (left + right) // 2
④ COMPARE
if nums[mid] == target: return mid
elif nums[mid] < target: left = mid + 1
else: right = mid - 1
⑤ RETURN
return -1
▼ your implementation ▼
Verify your solution:
Practice until you don't need to look. The green highlights are the nuances to burn into memory.
PATTERN ▸ Recursive halving O(log n) · O(log n)
① BASE CASE
if left > right: return -1
② MID
mid = (left + right) // 2
③ COMPARE & RECURSE
if nums[mid]==target: return mid
elif nums[mid]<target: return search(nums,target,mid+1,right)
else: return search(nums,target,left,mid-1)
▼ your implementation ▼
Verify your solution: