6 drills · 6 pattern exercises · 7 micro drills
Patterns used in this topic, with difficulty breakdown.
Look for a specific number in a sorted list by repeatedly cutting the search area in half.
All 6 drills grouped by pattern. Each includes prompt, solution, and complexity.
In plain English: Look for a specific number in a sorted list by repeatedly cutting the search area in half.
Each comparison eliminates half the remaining elements — log2(n) halves is all you ever need to find any element or prove it absent.
Prompt
Given a sorted array and a target value, return the index of the target or -1 if not found.
Solution
def binary_search(a, target):
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = (lo + hi) // 2
if a[mid] == target:
return mid
elif a[mid] < target:
lo = mid + 1 # target is in right half
else:
hi = mid - 1 # target is in left half
return -1
# Test: binary_search([1,3,5,7,9,11], 7) == 3
# Test: binary_search([1,3,5,7,9,11], 4) == -1In plain English: Find the largest integer whose square is less than or equal to x.
Binary search on the answer space [0, x]: if mid*mid <= x, the answer is at least mid; if mid*mid > x, it is less than mid.
Prompt
Given a non-negative integer x, compute floor(sqrt(x)) without using math.sqrt.
Solution
def my_sqrt(x):
if x < 2:
return x
lo, hi = 1, x // 2
while lo <= hi:
mid = (lo + hi) // 2
sq = mid * mid
if sq == x:
return mid
elif sq < x:
lo = mid + 1 # answer might be larger
else:
hi = mid - 1 # answer must be smaller
return hi # hi is floor(sqrt(x))
# Test: my_sqrt(8) == 2
# Test: my_sqrt(16) == 4
# Test: my_sqrt(0) == 0In plain English: Find any element in an array that is bigger than both its neighbors.
If a[mid] < a[mid+1], a peak must exist to the right (values must eventually drop at the boundary). Move toward the rising side.
Prompt
Given an array where no two adjacent elements are equal, find any peak element (strictly greater than its neighbors). Return its index.
Solution
def find_peak(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < a[mid + 1]:
lo = mid + 1 # peak is to the right
else:
hi = mid # mid could be the peak
return lo
# Test: find_peak([1,2,3,1]) == 2
# Test: find_peak([1,2,1,3,5,6,4]) in (1, 5)In plain English: Find the smallest number in a sorted array that has been rotated (e.g., [4,5,6,7,0,1,2]).
Compare mid to hi: if a[mid] > a[hi], the rotation point (minimum) is to the right; otherwise it is at mid or to the left.
Prompt
Given a rotated sorted array with unique elements, find the minimum element.
Solution
def find_min(a):
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] > a[hi]:
lo = mid + 1 # min is in right half
else:
hi = mid # mid could be the min
return a[lo]
# Test: find_min([4,5,6,7,0,1,2]) == 0
# Test: find_min([3,4,5,1,2]) == 1
# Test: find_min([1,2,3]) == 1In plain English: Find the leftmost position where you could insert a number into a sorted list and keep it sorted.
Bisect-left finds the first position where target could go — when the loop ends, lo points to the insertion point because all elements left of lo are strictly less.
Prompt
Given a sorted array and a target, return the index where the target would be inserted to keep the array sorted (bisect_left).
Solution
def search_insert(a, target):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < target:
lo = mid + 1
else:
hi = mid # a[mid] >= target, could be the answer
return lo
# Test: search_insert([1,3,5,6], 5) == 2
# Test: search_insert([1,3,5,6], 2) == 1
# Test: search_insert([1,3,5,6], 7) == 4In plain English: Find where a number first and last appears in a sorted list that may have duplicates.
Two binary searches: bisect-left finds the first occurrence, bisect-right minus one finds the last — both run in O(log n).
Prompt
Given a sorted array with duplicates and a target, find the first and last index of the target. Return [-1, -1] if not found.
Solution
def search_range(a, target):
def bisect_left(a, t):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < t:
lo = mid + 1
else:
hi = mid
return lo
def bisect_right(a, t):
lo, hi = 0, len(a)
while lo < hi:
mid = (lo + hi) // 2
if a[mid] <= t:
lo = mid + 1
else:
hi = mid
return lo
left = bisect_left(a, target)
right = bisect_right(a, target) - 1
if left <= right and left < len(a) and a[left] == target:
return [left, right]
return [-1, -1]
# Test: search_range([5,7,7,8,8,10], 8) == [3, 4]
# Test: search_range([5,7,7,8,8,10], 6) == [-1, -1]6 exercises: spot the signals, pick the method, avoid the trap.
Given a sorted array and a target value, return the index of the target or -1 if not found.
Signals
lo=0, hi=n-1. Compare mid. If target < mid, search left; if target > mid, search right. O(log n).
Trap
Watch the off-by-one: lo <= hi (not lo < hi). And mid = lo + (hi-lo)//2 avoids overflow.
Given a sorted array and a target, return the index where the target would be inserted.
Signals
Standard binary search but return lo when not found. lo always points to the insert position. O(log n).
Trap
This is bisect_left. Know the difference between bisect_left and bisect_right.
Given a sorted array with duplicates and a target, find the first and last index of the target.
Signals
Run bisect_left (find first >=) and bisect_right (find first >) separately. Both O(log n).
Trap
A single binary search that finds one occurrence then scans linearly is O(n) worst case for all-same arrays.
Compute floor(sqrt(x)) without using math.sqrt.
Signals
Binary search on [0, x]. If mid² <= x, answer is at least mid (search right). O(log x).
Trap
This is 'binary search on the answer' — a crucial pattern. The sorted array is implicit.
Given an array where no two adjacent elements are equal, find any peak element.
Signals
Compare mid with mid+1. Move toward the larger side — a peak is guaranteed there. O(log n).
Trap
Linear scan finding max is O(n). Binary search works because you can always move toward a guaranteed peak.
Given a rotated sorted array with unique elements, find the minimum element.
Signals
Compare a[mid] with a[hi]. If a[mid] > a[hi], rotation point is right. O(log n).
Trap
Compare with a[hi] not a[lo]. Comparing with a[lo] doesn't reliably tell you which side the min is on.
7 quick recall drills to reinforce this topic.
The standard binary search template. Foundation for all logarithmic search problems.
lo, hi = 0, len(a) - 1
while lo <= hi:
mid = lo + (hi - lo) // 2
if a[mid] == target: return mid
elif a[mid] < target: lo = mid + 1
else: hi = mid - 1Move toward the higher neighbor — a peak must exist on that side. Uses lo < hi (not <=) and hi = mid (not mid-1).
lo, hi = 0, len(a) - 1
while lo < hi:
mid = (lo + hi) // 2
if a[mid] < a[mid + 1]:
lo = mid + 1
else:
hi = mid
return loLeft boundary search finds the first occurrence. Key for range queries and count problems.
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] < target: lo = mid + 1
else: hi = mid
return loRight boundary search finds the insertion point after equals. Paired with bisect_left for range counting.
lo, hi = 0, len(a)
while lo < hi:
mid = lo + (hi - lo) // 2
if a[mid] <= target: lo = mid + 1
else: hi = mid
return loThree-way partition handles duplicates efficiently. Classic for sort-colors type problems.
lo, mid, hi = 0, 0, len(a) - 1
while mid <= hi:
if a[mid] < pivot:
a[lo], a[mid] = a[mid], a[lo]
lo += 1; mid += 1
elif a[mid] == pivot:
mid += 1
else:
a[mid], a[hi] = a[hi], a[mid]
hi -= 1Write-pointer compaction for sorted arrays. Returns new length.
w = 1
for i in range(1, len(a)):
if a[i] != a[i-1]:
a[w] = a[i]
w += 1
return wTwo-pointer write keeps unique elements in-place with O(1) space. Core array cleanup technique.
# Two-pointer write — keep unique in-place
w = 1
for r in range(1, len(a)):
if a[r] != a[r - 1]:
a[w] = a[r]
w += 1
# a[:w] has unique elements