To ace your coding interview for a software engineering job, you’ll need to understand binary search. It comes up frequently in coding interviews and is fundamental to many other algorithms too.
Let’s take a look at some typical binary search questions.
6 typical binary search interview questions
Given an array of integers nums that is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1.
Given the sorted rotated array nums of unique elements, return the minimum element of this array in O(log n) time.
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right.
The first integer of each row is greater than the last integer of the previous row.
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order with O(log n) runtime complexity.
Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Below, we take a look at 50 binary search questions and provide you with links to high quality solutions to them.
This is an overview of what we’ll cover:
- Easy binary search interview questions
- Medium binary search interview questions
- Hard binary search interview questions
- Binary search basics
- Binary search cheat sheet
- How to prepare for a coding interview
Let's get started.
You might be tempted to try to read all of the possible questions and memorize the solutions, but this is not feasible. Interviewers will always try to find new questions, or ones that are not available online. Instead, you should use these questions to practice the fundamental concepts of binary search.
As you consider each question, try to replicate the conditions you’ll encounter in your interview. Begin by writing your own solution without external resources in a fixed amount of time.
If you get stuck, go ahead and look at the solution, but then try the next one alone again. Don’t get stuck in a loop of reading as many solutions as possible! We’ve analysed dozens of questions and selected ones that are commonly asked and have clear and high quality answers.
Here are some of the easiest questions you might get asked in a coding interview. These questions are often asked during the “phone screen” stage, so you should be comfortable answering them without being able to write code or use a whiteboard.
Question 1: Search insert position
Question 2: Sqrt(x)
Question 3: First bad version
Question 4: Intersection of two arrays
Question 5: Valid perfect square
Question 6: Guess number higher or lower
Question 7: Arranging coins
Question 8: Binary search
Question 9: Find smallest letter greater than target
Question 10: Peak index in a mountain array
Question 11: Count negative numbers in a sorted matrix
Question 12: Find the distance value between two arrays
Question 13: Kth missing positive number
Here are some moderate-level questions that are often asked in a video call or onsite interview. You should be prepared to write code or sketch out the solutions on a whiteboard if asked.
Question 14: Search in a rotated sorted array
Question 15: Find first and last position of element in sorted array
Question 16: Search a 2D matrix
Question 17: Search in rotated sorted array II
Question 18: Find minimum in rotated sorted array
Question 19: Find peak element
- Text guide (Techie Delight)
- Video guide (Kevin Naughton Jr.)
- Video guide (Errichto)
- Code example (gangan)
Question 20: Count complete tree nodes
Question 21: Search a 2D matrix II
Question 22: Longest increasing subsequence
Question 23: H-index II
Question 24: Random pick with weight
Question 25: Heaters
Question 26: Kth smallest element in a sorted matrix
Question 27: Single element in a sorted array
Question 28: Find K closest elements
Question 29: Koko eating bananas
Question 30: Online election
Question 31: Time based key-value store
Question 32: Capacity to ship packages within D days
Similar to the medium section, these more difficult questions may be asked in an onsite or video call interview. You will likely be given more time if you are expected to create a full solution.
Question 33: Median of two sorted arrays
Question 34: Count of smaller numbers after self
Question 35: Find minimum in rotated sorted array II
Question 36: Russian doll envelopes
Question 37: Max sum of rectangle no larger than K
Question 38: Split array largest sum
Question 39: Smallest good base
Question 40: Reverse pairs
Question 41: Kth smallest number in multiplication table
Question 42: Random pick with blacklist
Question 43: Find K-th smallest pair distance
Question 44: K-th smallest prime fraction
Question 45: Preimage size of factorial zeroes function
Question 46: Nth magical number
Question 47: Longest duplicate substring
Question 48: Maximum profit in job scheduling
Question 49: Find in mountain array
Question 50: Online majority element in subarray
In order to crack questions about binary search, you’ll need to have a strong understanding of the algorithm, how it works, and when to use it.
4.1 What is binary search?
Binary search is one of the fastest search algorithms because it halves the search space with each iteration. Binary search requires an ordered set that also has constant access times. This means that, of all the basic data structures, only sorted arrays are suitable for binary search.
Here’s how binary search halves the search space with each iteration:
- Find the middle element in the current search space. If this middle element is the target element, then return its index and stop the search.
- Else, determine whether the target element is to the left or right of the middle element, and reduce the search space to that half containing the element.
- Repeat the process on the halved search space: identify the middle element, return its index if it’s the target element, or determine which half of the search space the element will be in, and reduce the search space to that half.
- This search will continue until the target element is found or as long as there are items in the search space. If the search space contains no items, the algorithm has failed to find the target element in the array, and returns -1.
Let's search for the number 7 in the following sorted array, tracing the first three iterations:
On the first iteration our search space runs from index 0 to index 6, which makes 3 the middle index. The value at index 3 is 5 – this tells us that our target value 7 must be somewhere in the upper (or right) half of the array. We reduce the search space to the right half from index 4 to index 6, making index 5 the new middle. Index 5 has a value of 9, meaning our target value 7, being less than 9, must be in the left half of this reduced search space. So we halve the search space again to the left half, from index 4 to index 4 – which also makes index 4 the new middle. This new middle has the value of 7 that we are looking for, so we found our item at index 4.
4.1.1 Use cases for binary search (Java, Python, C++)
Binary search has a limited set of use cases:
- It is used to quickly find the index of an item in a long list. For example, a database index might contain 1,000,000 items. A binary search can find the item within 20 steps (log2 n time).
- This can be extended to finding ranges too. Given a sorted array of net wealth, all the billionaires can be found by determining the index of the first billionaire value. The range from this index to the end of the list will be all the billionaires.
- It is also used to find the index for insert and delete operations on a sorted array.
4.1.2 Example implementation
The implementation for binary search is straightforward, however there are some details we have to pay careful attention to.
We need to be careful when calculating the midpoint. It is tempting to calculate the midpoint as (beg + end) / 2, but this approach has two issues: First, adding the two numbers together can result in an overflow if they are both large. To avoid this, we add half the space size to the beginning. Second, we have to ensure mid is an integer value to be able to use it as an index. In Python the double forward slash (//) can be used to perform integer division. In other languages, a math “floor” routine can be used.
We also have to be careful of the while condition. If we specified beg < end (not including the end), then our example earlier would have failed to find the 7. The search space shrunk to one item on the third iteration, making the beginning and end the same item. To avoid this error, we use beg <= end.
4.1.3 How binary search compares to other algorithms
In terms of speed, only hash maps are faster than binary search, since hash maps can determine whether an item is in a set in constant time. However, hashing cannot tell us the next smallest or biggest item based on the item searched for. Hashing also cannot give us all the items in a given range, or the smallest or biggest item in the array.
A drawback of binary searching is that it requires a sorted array, because sorted arrays have linear insert and delete time complexities. The alternative is unsorted arrays with constant insertion and deletions, but with linear search time. Even though linear searching does have excellent locality of reference for the CPU cache, this locality is not enough to out perform binary search.
A binary search tree (BST) offers better insertion and deletion times, but BSTs can become degenerate (when every parent node has just one child node), which reduces searching time to linear. Balanced trees are a solution to keep search time to log_2 n, but finding ranges in a balanced tree is harder, and finding the smallest or largest element is no longer constant time.
Need a boost in your career as a software engineer?
If you want to improve your skills as an engineer or leader, tackle an issue at work, get promoted, or understand the next steps to take in your career, book a session with one of our software engineering coaches.
You can download the cheat sheet here.
5.1 Related algorithms and techniques
5.2 Cheat sheet explained
The cheat sheet above is a summary of information you might need to know for an interview, but it’s usually not enough to simply memorize it. Instead, aim to understand each result so that you can give the answer in context.
The cheat sheet is broken into time complexity and space complexity (the processing time and memory requirements for binary search). Binary search is related to several data structures, which are also included in the cheat sheet.
For more information about time and space requirements of different algorithms, read our complete guide to big-O notation and complexity analysis.
5.2.1 Time complexity
As the search space is halved with each iteration, the time complexity of binary search is log_2. In the worst case, we won't find our item and the search space will shrink to size zero (0) once all possible iterations have been completed, giving a complexity of O(log_2 n). On average, some iterations are completed, reducing time to O(log_2 n). At best, the item we are looking for might be at the middle index, for O(1).
Finding the smallest or biggest item in a sorted array is O(1) and finding values in a range is O(log_2 n).
5.2.2 Space complexity
The algorithm only needs to store the beginning and end indices of the search space, whether ten items or a million items are being searched, giving binary search a space complexity of O(1).
5.2.3 Related algorithms and data structures: arrays and binary search trees
Binary search requires the array it searches to be sorted. Sorted arrays only have constant time insertions when inserting at the end of the array. When inserting anywhere else in the array, all the items after the insertion point have to move one index right to accommodate the new item. This results in an average insertion time complexity of O(n).
Similarly, deleting the last item in a sorted array is constant. But deleting from anywhere else in the array requires all the items after the deletion point to move one index left to fill the gap of the removed item. This also results in an average time complexity of O(n) when deleting.
When inserting and deleting times are a concern, a binary search tree (BST) can be used. Searching a BST is much like binary search:
- Search starts at the root node. If the current node is the target value, it is returned and the search is stopped.
- Else, if the target value is less than the current node, the search is continued on the left subtree. If the target value is greater than the current node, the search is continued on the right subtree.
- These steps are repeated until the target value is found or as long as there are more subtrees, else return -1.
In this way, moving down each layer of the tree is like the iterations of a binary search. Let’s take a look at an example, searching for 7 again:
We start with the root node, which has a value of 5. This is not the 7 we are looking for, and since 7 is bigger than 5, we go to the right subtree. The value of the current node on the right subtree is 9 – not the 7 we are looking for, and as our target value is smaller than 9, we go to the left subtree. The leaf of the left subtree is compared to our target value 7, and since they match, the leaf node is returned.
Just like our array search, the search space is halved with each iteration for a time complexity of O(log_2 n). But adding a node with a value of 4 would be straightforward, as it would be the right-hand child of 3, giving insertion constant time.
6.1 Practice on your own
Before you start practicing interviews, you’ll want to make sure you have a strong understanding of not only binary search but also the rest of the relevant algorithms and data structures. You’ll also want to start working through lots of coding problems.
Check out the guides below for lists of questions organized by difficulty level, links to high-quality answers, and cheat sheets.
- Breadth-first search
- Depth-first search
- Dynamic programming
- Greedy algorithm
- Divide and conquer
Data structure guides
- Linked lists
- Stacks and Queues
- Coding interview examples (with solutions)
To get used to an interview situation, where you’ll have to code on a whiteboard, we recommend solving the problems in the guides above on a piece of paper or google doc.
6.2 Practice with others
However, sooner or later you’re probably going to want some expert interventions and feedback to really improve your coding interview skills.
That’s why we recommend practicing with ex-interviewers from top tech companies. If you know a software engineer who has experience running interviews at a big tech company, then that's fantastic. But for most of us, it's tough to find the right connections to make this happen. And it might also be difficult to practice multiple hours with that person unless you know them really well.
Here's the good news. We've already made the connections for you. We’ve created a coaching service where you can practice 1-on-1 with ex-interviewers from leading tech companies. Learn more and start scheduling sessions today.