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
- 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
4.1 Refresh your knowledge
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. Check out our guides for detailed explanations and useful cheat sheets.
- Depth-first search
- Breadth-first search
- Binary search
- Dynamic programming
- Greedy algorithm
- Divide and conquer
Data structure guides:
4.2 Practice on your own
Once you’re confident in all of these, you’ll want to start working through lots of coding problems.
For binary search you can obviously use the questions we’ve listed above. For the other algorithms you need to know, check out the rest of this series:
- Depth-first search interview questions
- Breadth-first search interview questions
- Sorting interview questions
- Dynamic programming interview questions
- Greedy algorithm interview questions
- Backtracking interview questions
- Divide and conquer interview questions
We also recommend working through our list of 73 data structure interview questions.
One of the main challenges of coding interviews is that you have to communicate what you are doing as you are doing it. Talking through your solution out loud is therefore very helpful. This may sound strange to do on your own, but it will significantly improve the way you communicate your answers during an interview.
It's also a good idea to work on a piece of paper or google doc, given that in the real interview you'll have to code on a whiteboard or virtual equivalent.
3.3 Practice with others
Of course, if you can practice with someone else playing the role of the interviewer, that's really helpful. But 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.
Any questions about binary search interview questions?
If you have any questions about binary search or coding interviews in general, don't hesitate to ask them in the comments below. All questions are good questions, so go ahead!