Binary Search

Use when you need to locate an element or boundary in a sorted array efficiently in
O(log n) time.

Use when you need to locate an element or boundary in a sorted array efficiently in O(log n) time.

Keywords for identifying Binary Search Problems

→ Sorted array / sorted input
→ Find target or boundary
→ First / last occurrence
→ Smallest / largest index that satisfies condition
→ Monotonic condition (true → false or false → true)

Template

Template · python

lhs = 0 # left pointer
rhs = len(nums)-1 # right pointer

"""
we use lhs + 1 < rhs to ensure:
- lhs pointer always stays on left side
- rhs pointer always stays on right side
- leave space for a mid pointer in between
this makes post processing stage easier to think about
"""
while lhs + 1 < rhs:
	"""
	we can replace "(lhs+rhs)//2" with "lhs+(rhs-lhs)//2" for languages
	where we have to worry about overflow like C/C++
	"""
	mid = (lhs + rhs)//2
	if nums[mid] == target:
		return mid
	elif nums[mid] < target:
		lhs = mid
	else:
		rhs = mid
	
"""
post processing:
lhs pointer should always be next to rhs pointer here eg) L R
with 1 exception when lhs and rhs pointer are ontop of each other in an array with just 1 element
"""
if nums[lhs] == target:
	return lhs
elif nums[rhs] == target:
	return rhs
else:
	return -1 # target not found

Try questions yourself first before looking at solution 🙂

Examples

Now drill spotting it under time pressure

Open the daily quiz — knowing the template isn’t enough; you have to recognize when to reach for it.

→

Template

Template · python

lhs = 0 # left pointer
rhs = len(nums)-1 # right pointer

"""
we use lhs + 1 < rhs to ensure:
- lhs pointer always stays on left side
- rhs pointer always stays on right side
- leave space for a mid pointer in between
this makes post processing stage easier to think about
"""
while lhs + 1 < rhs:
	"""
	we can replace "(lhs+rhs)//2" with "lhs+(rhs-lhs)//2" for languages
	where we have to worry about overflow like C/C++
	"""
	mid = (lhs + rhs)//2
	if nums[mid] == target:
		return mid
	elif nums[mid] < target:
		lhs = mid
	else:
		rhs = mid
	
"""
post processing:
lhs pointer should always be next to rhs pointer here eg) L R
with 1 exception when lhs and rhs pointer are ontop of each other in an array with just 1 element
"""
if nums[lhs] == target:
	return lhs
elif nums[rhs] == target:
	return rhs
else:
	return -1 # target not found

Try questions yourself first before looking at solution 🙂

Examples