Binary Search

#binarysearch

Problems

# Problem Difficulty Hint Tags
20 Binary Search - LeetCode Easy
Hint Template binary search problem. Binary search can only be executed on sorted items.
 #array #binarysearch
74 Search a 2D Matrix - LeetCode Medium
HintRun two binary searches, one to find the row and one to find the number in the row.
#array #binarysearch #matrix
875 Koko Eating Bananas - LeetCode Medium
HintWhat is the upper and lower bounds on k?How do we calculate the time it takes to eat one pile? How do we move the pointers based on the time it took to eat the bananas.
#array #binarysearch

Binary search is a technique used to efficiently sort items on a sorted list. It works by dividing the search space in half until you reach your desired target.

l, r = 0, len(nums) - 1 

while l <= r:
	m = (l + r) // 2
	if nums[m] < target:
		l = m + 1
	elif nums[m] > target:
		r = m - 1
	else:
		return m

return -1

The key to binary search is finding when and where you need to partition the elements.

Anytime you see a sorted list where you need to search, or they are asking for O(logn) time, it is likely binary search.