LeetCode 704 · Binary Search · concepts: searching, modified-binary-search
Problem
Given a sorted array and a target, return its index, or −1 if absent. O(log n) required.
nums = [-1,0,3,5,9,12], target = 9 -> 4
Approach — the canonical template
Maintain a [l, r] window of where the target could be. Compare the middle; because the array is sorted, one comparison discards half the remaining range.
def search(nums, target):
l, r = 0, len(nums) - 1
while l <= r:
mid = l + (r - l) // 2 # avoids overflow in fixed-width languages
if nums[mid] == target:
return mid
elif nums[mid] < target:
l = mid + 1 # target is in the right half
else:
r = mid - 1 # target is in the left half
return -1Time O(log n), space O(1).
The three details people get wrong
while l <= r(not<) — with<, a single-element window is never examined, missing targets.mid + 1/mid - 1— moving pastmid(already checked) is what guarantees the window shrinks;l = midcan loop forever.l + (r - l) // 2— mathematically equal to(l + r) // 2but can’t overflow a fixed-width int.
Key insight
Sorted data + one comparison that eliminates half → O(log n). Every binary-search variant is this loop with a different “which half can I discard?” rule. Master the invariant (target ∈ [l, r]) and the boundary updates; the variations below only change the comparison.
Related
- concepts: searching, modified-binary-search
- next: Search a 2D Matrix
Jump to a subject
Software engineering
Infrastructure & security
Computer science
Hardware & engineering