50 binary search interview questions [easy, medium, hard]

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.

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:

1. Easy binary search interview questions
2. Medium binary search interview questions
3. Hard binary search interview questions
4. Binary search basics
5. Binary search cheat sheet
6. How to prepare for a coding interview

Let's get started.

Click here to practice coding interviews with ex-FAANG interviewers

1. Easy binary search interview questions

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.

2. Medium binary search interview questions

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.

3. Hard binary search interview questions

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.

4. Binary search basics

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:

1. 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.
2. 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.
3. 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.
4. 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.

5. Binary search cheat sheet

You can download the cheat sheet here.

5.1 Related algorithms and techniques

• Jump search

• Exponential search

• Fibonacci search

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:

1. Search starts at the root node. If the current node is the target value, it is returned and the search is stopped.
2. 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.
3. 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. How to prepare for a coding interview

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.

Algorithm guides

• Breadth-first search
• Depth-first search
• Sorting
• Dynamic programming
• Greedy algorithm
• Backtracking
• Divide and conquer

Data structure guides

• Arrays
• Strings
• Linked lists
• Stacks and Queues
• Trees
• Graphs
• Maps
• Heap
• 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.