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.
Click here to practice coding interviews with exFAANG 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.
Question 1: Search insert position
 Text guide (GeeksForGeeks)
 Video guide (NeetCode)
 Video guide (TECH DOSE)
Question 2: Sqrt(x)
 Text guide (GoodTecher)
 Video guide (Terrible Whiteboard)
 Code example (AlexTheGreat)
Question 3: First bad version
 Text guide (Medium/Mac Sampson)
 Video guide (Kevin Naughton Jr.)
 Code example (Cheng_Zhang)
Question 4: Intersection of two arrays
 Text guide (AfterAcademy)
 Code example (divingboy89)
Question 5: Valid perfect square
 Text guide (Dev.to/Aroup)
 Video guide (TECH DOSE)
 Code example (LeetCode)
Question 6: Guess number higher or lower
 Text guide (Dev.to/Mridu Bhatnagar)
 Video guide (Coding Decoded)
 Code example (StefanPochmann)
Question 7: Arranging coins
 Text guide (just4once)
 Video guide (Naresh Gupta)
 Code example (ratchapongt)
Question 8: Binary search
 Text guide (AminiCK)
 Video guide (Nick White)
 Code example (LeetCode)
Question 9: Find smallest letter greater than target
 Text guide (Callicoder)
 Video guide (Eric Programming)
 Code example (nrl)
Question 10: Peak index in a mountain array
 Text guide (Memogrocery)
 Video guide (Nick White)
 Code example (lee215)
Question 11: Count negative numbers in a sorted matrix
 Text guide (TechieDelight)
 Video guide (Sai Anish Malla)
 Code example (gthor10)
Question 12: Find the distance value between two arrays
 Text guide (TutorialCup)
 Video guide (onepunchcoder)
 Code example (LeetCode)
Question 13: Kth missing positive number
 Text guide (TutorialCup)
 Text guide (The Startup)
 Video guide (Algorithms Made Easy)
 Code example (lee215)
2. Medium binary search interview questions
Here are some moderatelevel 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
 Text guide (Educative)
 Video guide (NeetCode)
 Video guide (Errichto)
 Code example (1337beef)
Question 15: Find first and last position of element in sorted array
 Text guide (Enjoy Algorithms)
 Video guide (Nick White)
 Code example (stellari)
Question 16: Search a 2D matrix
 Text guide (TheLeanProgrammer)
 Video guide (NeetCode)
 Code example (LeetCode)
Question 17: Search in rotated sorted array II
 Text guide (Programcreek)
 Video guide (Knowledge Center)
 Code example (LeJas)
Question 18: Find minimum in rotated sorted array
 Text guide (Callicoder)
 Video guide (Nick White)
 Video guide (NeetCode)
 Code example (water1111)
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
 Text guide (Medium/AlgoMonster)
 Video guide (TECH DOSE)
 Code example (StefanPochmann)
Question 21: Search a 2D matrix II
 Text guide (Dev.to/seanpgallivan)
 Video guide (Algorithms Made Easy)
 Code example (chicm)
Question 22: Longest increasing subsequence
 Text guide (Algorithmsandme)
 Video guide (take U forward)
 Code example (dietpepsi)
Question 23: Hindex II
 Text guide (Evelynn)
 Video guide (TECH DOSE)
 Code example (LeJas)
Question 24: Random pick with weight
 Text guide (Massive Algorithms)
 Video guide (TECH DOSE)
 Code example (LATTES)
Question 25: Heaters
 Text guide (just4once)
 Video guide (happygirlzt)
 Code example (shawngao)
Question 26: Kth smallest element in a sorted matrix
 Text guide (Medium/Ayoub Omari)
 Video guide (Winson Ye)
 Code example (YuanGao)
Question 27: Single element in a sorted array
 Text guide (Web Rewrite)
 Video guide (TECH DOSE)
 Code example (baguette)
Question 28: Find K closest elements
 Text guide (Zirui)
 Video guide (Ren Zhang)
 Code example (lee215)
Question 29: Koko eating bananas
 Text guide (Dev.to/codingpineapple)
 Video guide (Michael Muinos)
 Code example (GraceMeng)
Question 30: Online election
 Text guide (Massive Algorithms)
 Video guide (Cat Racket Code)
 Code example (lee215)
Question 31: Time based keyvalue store
 Text guide (Linlaw Techblog)
 Video guide (Michael Muinos)
 Code example (votrubac)
Question 32: Capacity to ship packages within D days
 Text guide (GeeksForGeeks)
 Video guide (code Explainer)
 Code example (lee215)
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.
Question 33: Median of two sorted arrays
 Text guide (Medium/hamid)
 Video guide (NeetCode)
 Code example (MissMary)
Question 34: Count of smaller numbers after self
 Text guide (Seanforfun)
 Video guide (happygirlzt)
 Code example (mayanist)
Question 35: Find minimum in rotated sorted array II
 Text guide (GraceMeng)
 Video guide (Naresh Gupta)
Question 36: Russian doll envelopes
 Text guide (Dev.to/seanpgallivan)
 Video guide (Algorithms Made Easy)
 Code example (TianhaoSong)
Question 37: Max sum of rectangle no larger than K
 Text guide (just4once)
 Video guide (Happy Coding)
 Code example (javachao)
Question 38: Split array largest sum
 Text guide (Nitish Chandra)
 Video guide (happygirlzt)
 Code example (dax1ng)
Question 39: Smallest good base
 Text guide (just4once)
 Code example (wgl)
Question 40: Reverse pairs
 Text guide (fun4LeetCode)
 Video guide (take U forward)
 Code example (Tutorialspoint)
Question 41: Kth smallest number in multiplication table
 Text guide (seanforfun)
 Text guide (LeetCode)
 Video guide (Coders Camp)
 Code example (shawngao)
Question 42: Random pick with blacklist
 Text guide (Massive Algorithms)
 Video guide (babybear4812)
 Code example (wangzi6147)
Question 43: Find Kth smallest pair distance
 Text guide (Medium/Timothy Huang)
 Video guide (code Explainer)
 Code example (fun4LeetCode)
Question 44: Kth smallest prime fraction
 Text guide (seanforfun)
 Video guide (Happy Coding)
 Code example (fun4LeetCode)
Question 45: Preimage size of factorial zeroes function
 Text guide (fun4LeetCode)
 Text guide (just4once)
 Code example (walkccc)
Question 46: Nth magical number
 Text guide (just4once)
 Video guide (Shivam Patel)
 Code example (lee215)
Question 47: Longest duplicate substring
 Text guide (Medium/Anshika Bhargava)
 Video guide (TECH DOSE)
 Code example (lee215)
Question 48: Maximum profit in job scheduling
 Text guide (Tutorials point)
 Video guide (Timothy H Chang)
 Code example (lee215)
Question 49: Find in mountain array
 Text guide (lee215)
 Video guide (babybear4812)
 Code example (Medium/Yinfang)
Question 50: Online majority element in subarray
 Text guide (Massive Algorithms)
 Code example (lee215)
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:
 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.
5. Binary search cheat sheet
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 bigO 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 righthand 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 highquality answers, and cheat sheets.
Algorithm guides
 Breadthfirst search
 Depthfirst 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 exinterviewers 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 1on1 with exinterviewers from leading tech companies. Learn more and start scheduling sessions today.