Ultimate Binary Search Guide With 10+ Examples
My goal with this is to make the explanations as simple to understand, concise, and applicable as I can so that it's easy to not only learn but also to get a quick refresher when needed.
We use binary search when the input (usually array) is sorted and we need to find an item in that array in an efficient way. Questions might hint towards using binary search if it states it wants a solution in O(log(n)) time complexity.
When approaching binary search problems, the first thing you should think about are where to set your two pointers, aka the initital boundary of the problem so that you include all possible answers. Usually, you will have one set at the first index and one at the last, but that's not always the case:
# Normal Boundary
left, right = 0, len(nums) - 1
# Other Boundaries in Following Examples
left, right = 1, n
left, right = 0, len(nums)
left, right = 0, max(nums)
left, right = max(nums), sum(nums)
Next, it's important to understand the conditions to shrink our boundaries. Generally, we want to use logic that excludes mid. Also, for more complex questions, it is common to put the logic for the conditions of shinking the boundaries in a helper function. With this, there are 2 "templates" that appear:
# Lower Mid Template
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid = 1
else:
right = mid
# Upper Mid Template
while left < right:
mid = left + (right - left + 1) // 2
if nums[mid] > target:
right = mid - 1
else:
left = mid
If you are stuck, try thinking of the situation when there are only 2 elements left. Did the boundary shrink correctly?
Also, it's super important to keep the context of the problem in mind when figuring out the conditions to move the pointers in our binary search. We'll talk about this in the below examples.
Finally, remember to think about how to return the answer of our binary search. Many times, it may be as simple as returning the left or right pointer, but many other times, you may need to return your answer based on some condition(s).
Problems & Walkthrough
Here are some example questions taken from Leetcode with walkthroughts of each one, sorted from easiest to hardest.
704. Binary Search
This is the most basic binary search problem! Let's go through how to solve this systematically. To start, we can determine that in order to include ALL possible answers, we need to include all elements in the array—which means our pointers will be at the first and last index of the input array.
Our conditions to shrink the boundaries are as basic as it gets, and we can quite literally just follow the basic logic of either of the two templates. Here is the code:
def binarySearch(nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left if nums[left] == target else -1
278. First Bad Version
First, we must determine the boundaries of the pointers we will use so that we include ALL possible answers. To do this, we have to include all elements from 1 to n since any one of them can be the first bad version—thus, we set our pointers to the first version (1) and the final version (n).
Our conditions to shrink the boundaries will rely on the result of the API call provided. Let's say we call the API on some version and it returns true. That tells us we have found a bad version, but we do not know if it is the first one, which means we should look at previous versions to the left of that version to see if there is an earlier bad version. On the flipside, if the API call returns false, that tells us we did not find a bad version, which means we should look at following versions to the right of that version to possibly find a bad version.
def firstBadVersion(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if not isBadVersion(mid):
left = mid + 1
else:
right = mid
return left
374. Guess Number Higher or Lower
To start, we need to find the boundaries of the pointers we will use so that we include ALL possible answers. To do this, we have to include all elements from 1 to n since any one of them can be the right number—thus, we set our pointers to the first number (1) and the last number (n).
Our conditions to shrink the boundaries will rely on the result of the API call provided. Let's say we call the API on some number and it returns 1 (guess is lower than answer). That tells us that we need to search in the higher range, so we can increase our left pointer. If the API call returns -1, that means our guess was higher than the answer, so we need to decrease our right pointer.
def guessNumber(self, n: int) -> int:
left, right = 1, n
while left < right:
mid = left + (right - left) // 2
if guess(mid) == 1:
left = mid + 1
else:
right = mid
return left
35. Search Insert Position
Figuring out the boundaries is a bit tougher for this question than the previous ones so far. To make sure we are including ALL possible positions, we cannot simply just set the pointers to the first and last index of the input array. This is because we are able to insert a number after the last index, whcih means it goes out of bounds of our boundary. Thus, we need to make our boundary the first index and one after the last index.
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) #NOT len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
34. Find First and Last Position of Element in Sorted Array
This is a great questions to understand the 2 templates and how they work and how they can result in different answers. The boundaries are easy to figure out, and we can see that we use binary search twice. Once with finding the lower mid by using
mid = left + (right - left) // 2 and once with finding the upper mid by using
mid = left + (right - left + 1) // 2.
def searchRange(self, nums: List[int], target: int) -> List[int]:
res = []
if not nums:
return [-1, -1]
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid
res.append(left) if nums[left] == target else res.append(-1)
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left + 1) // 2
if nums[mid] > target:
right = mid - 1
else:
left = mid
res.append(right) if nums[right] == target else res.append(-1)
return res
367. Valid Perfect Square
To solve this, we need to determine if a number is a perfect square without using built-in square root functions. Since the value we’re looking for (the integer whose square might equal num) lies somewhere between 0 and num, our boundaries become left = 0 and right = num to make sure we include all possible answers.
Our condition to shrink the boundaries is straightforward: compute mid * mid and compare it with num. If mid * mid is too small, we need a bigger number, so we move left up. If it's too large, we shrink the search space by moving right down.
Eventually, when the boundaries shrink to a single number, we simply check whether left * left is equal to num. If it is, then num is a perfect square—otherwise, it’s not.
def isPerfectSquare(self, num: int) -> bool:
left, right = 0, num
while left < right:
mid = left + (right - left) // 2
if mid * mid < num:
left = mid + 1
else:
right = mid
return True if (left * left) == num else False
1283. Find the Smallest Divisor Given a Threshold
First, we need to figure out the boundaries of our pointers. Since our divisors can only be positive integers and we are looking for the smallest divisor, we know that we have to search from 1 to the max(arr) to find the smallest divisor.
Our conditions to shrink the boundary are pretty simple, but complex enough to where I think a helper function is useful. We can write helper function that checks if our divisor results in a sum that is equal to or below our threshold. If it does and returns true, we know that we have found an answer and thus need to see if there are any possible divisors lower than this one that work. If it returns false, then we know we need to increase our divisor to lower the threshold.
def smallestDivisor(self, nums: List[int], threshold: int) -> int:
left, right = 1, max(nums)
while left < right:
mid = left + (right - left) // 2
if not self.checkDivisor(mid, nums, threshold):
left = mid + 1
else:
right = mid
return left
def checkDivisor(self, divisor, nums, threshold):
total = 0
for num in nums:
total += math.ceil(num / divisor)
return total <= threshold
875. Koko Eating Bananas
In this problem, we want to find the minimum eating speed that lets Koko finish all banana piles within h hours. To include every possible answer, our boundaries must be between 1 (the slowest possible speed) and max(piles) (the speed needed to finish the largest pile in one hour).
Our conditions to shrink the boundary come from a helper function we will write. For a given speed, we calculate how many hours it would take Koko to finish all piles by summing up ceil(pile / speed) for each pile. If the total hours exceed h, the speed is too slow, so we increase left. If it fits within h, the speed works—which means we can shrink the space by lowering right to search for a smaller valid speed since we are looking for the minimum speed to finish all the piles.
Once left meets right, we’ve found the minimum speed that allows Koko to finish all the bananas in time.
def minEatingSpeed(self, piles: List[int], h: int) -> int:
left, right = 1, max(piles)
while left < right:
mid = left + (right - left) // 2
if not self.canFinish(mid, piles, h):
left = mid + 1
else:
right = mid
return left
def canFinish(self, speed, piles, h):
time = 0
for pile in piles:
time += math.ceil(pile / speed)
return True if time <= h else False
1011. Capacity To Ship Packages Within D Days
For this problem, we want to find the minimum ship capacity that allows us to deliver all packages within the given number of days. To include all possible answers, our boundaries must be from the heaviest package (since capacity must be at least this large) up to the sum of all packages (the case where we ship everything in one day).
Our condition to shrink the boundaries relies on a helper function. Given a capacity, we simulate the process: load packages until adding another one exceeds the capacity, then start a new day. If the total number of days needed becomes greater than the limit, the current capacity is too small and we must increase left. Otherwise, the capacity works, and we shrink our search space by moving right down.
Once the boundaries meet, the value at left represents the smallest possible capacity that allows all packages to be shipped within the required number of days.
def shipWithinDays(self, weights: List[int], days: int) -> int:
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if not self.canShip(mid, weights, days):
left = mid + 1
else:
right = mid
return left
def canShip(self, capacity, weights, days):
timeItTakes = 1
curCapacity = 0
for weight in weights:
if curCapacity + weight > capacity:
timeItTakes += 1
curCapacity = 0
curCapacity += weight
if timeItTakes <= days:
return True
else:
return False
1482. Minimum Number of Days to Make m Bouquets
This is pretty similar to the capacity to ship question, in that we need a function to check if the number we are currently processing works. But before I get into that, we first need to determine the boundaries of our pointers. We know that at the very minimum, we need to wait a day and at the very maximum, we need to wait for the flower to take the longest to bloom to make our bouquets. Thus, our left and right pointers will be at 1 and the max(arr) respectively.
Our conditions to shrink the boundary will rely on the helper function we write. We do this since once we find a day, we need to check to make sure that we can create the m bouquets with k adjacent flowers. If we can't, then that means we need to wait longer for more flowers to bloom, thus moving our left pointer up so we search for higher days. If we can, then we can shrink the boundary by moving our right pointer to possibly find a day that works that is even smaller than the one we already found—since we are looking for the minimum number of days it takes.
As for the return condition, we return -1 if we do not have enough flowers to create the required amount to make the bouquets.
def minDays(self, bloomDay: List[int], m: int, k: int) -> int:
left, right = 1, max(bloomDay)
while left < right:
mid = left + (right - left) // 2
if not self.canMake(mid, bloomDay, m, k):
left = mid + 1
else:
right = mid
return -1 if (m * k > len(bloomDay)) else left
def canMake(self, days, bloomDay, m, k):
numBouquets = 0
curBouquet = 0
for bloomTime in bloomDay:
bloomed = bloomTime - days
if bloomed <= 0: #<= 0 means flower has bloomed
curBouquet += 1
else: #needs to use adjacent flowers, so reset if cannot use
curBouquet = 0
if curBouquet == k:
numBouquets += 1
curBouquet = 0
if numBouquets >= m:
return True
else:
return False
2187. Minimum Time to Complete Trips
We must figure out the boundaries of our pointers first, which for this question, is a bit tougher to determine. We know that our lower boundary must be 1, since we need at least 1 unit of time to complete our trips. However, for our upper boundary, it's not as simple as sum(time) or max(time). Let's go through some examples to figure it out. If we have time = [5,10, 10], totalTrips = 9, then the answer is 25—which tells us max(time) doesn't work, but sum(time) does. However, if we take another example where time = [1], totalTrips = 4, then we can see that the answer is 4, which tells us that sum(time) and max(time) cannot be our upper boundary. This leads us to our answer, which is min(time) * totalTrips for our upper boundary. We use this as the upper boundary because in the worst case, we use the fastest bus to complete all of our trips.
As for the conditions to shrink our pointers, we know that if we can successfully finish all the trips given some time, then that means we can move our right pointer down so that we can search for a possible lower time that completes all the trips. If we cannot finish given some time, we need to move our left pointer up to find a time that we can finish all the trips.
def minimumTime(self, time: List[int], totalTrips: int) -> int:
left, right = 1, min(time) * totalTrips
while left < right:
mid = left + (right - left) // 2
if not self.canFinish(mid, time, totalTrips):
left = mid + 1
else:
right = mid
return left
def canFinish(self, curTime, time, totalTrips):
trips = 0
for t in time:
trips += (curTime // t)
return True if trips >= totalTrips else False