Binary Search Interview Questions & Tips for Senior Engineers

Binary Search Interview Questions & Tips

By Mike Mroczka | Last updated: June 18, 2024

What Is Binary Search?

Binary search is an efficient divide and conquer algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half, narrowing down the potential locations of the item until either the item is found or it's established that the item isn't in the list. This method of halving the interval is what gives the algorithm its name – “binary” refers to the “two directions” we can choose to go during the algorithm.

At each step, the algorithm compares the middle element in the search space with the target value. If they are equal, it returns the index of the middle element. If the target value is less than the middle element, the search continues on the lower half of the array. If the target value is greater, the search continues on the upper half. The process continues until the search space is empty or the target element is found.

The beauty of binary search is in its time complexity - O(log n), which makes it highly efficient for large datasets, significantly outperforming linear search methods that have a time complexity of O(n).

What's the Difference Between Binary Search and a Binary Search Tree?

Binary search is an algorithm used to find an element in a sorted array. A binary search tree, on the other hand, is a type of data structure that maintains elements in a manner where they can be searched, inserted, and deleted using the principles of binary search. Binary Search Trees aren't very common in interviews, but are worth knowing in case they show up.

Logarithms

Why They Matter

Scared of logarithms? If you like most people, you probably haven't worked with logarithms for a very long time if you ever even did it in the first place! That's okay! All you really need to know is a small number of facts to be comfortable talking about them in interviews.

The reason this is worth discussing is because many candidates don't appreciate the difference between time complexities involving logs. You've probably seen an example of time complexities plotted on a graph before, something like this:

The graph illustrates three time complexities: O(log N), O(N), and O(N log N). The difference in scale between O(log N) and O(N) is massive, not slight, as input sizes increase. This means if you can use a logarithmic algorithm it isn't "slightly better than linear" it is massively better. The operations needed for a logarithmic algorithm are infinitesimal compared to a linear algorithm.

O(N log N) represents log-linear time complexity. Candidates occasionally find it difficult to remember where it falls on the spectrum of complexities, but it helps to remember the implicit multiplication in the notation. It isn't O(N log N) it is O(N * log N). Thus, O(N log N) is larger than O(N) since we are multiplying it by something, yet it is still relatively small, as it's multiplied by the significantly smaller O(log N).

Why Is Binary Search Logarithmic?

Repeatedly dividing something creates a logarithmic function (note the emphasis on the word repeated here). If you divide something once, it does not change the asymptotic nature of the function. This code below would still be considered linear, not logarithmic:

PythonJavaC++

def linear(n):
  for i in range(n/2):
    print(i)

But if we are repeatedly dividing something, we are doing something inherently logarithmic with it. See the below code as an example:

PythonJavaC++

def logarithmic(n):
  while n > 1:
    n = n / 5
    print(n)

So in binary search, we can see that we are repeatedly dividing the array in half and exploring smaller and smaller sections of it. This gives us a logarithmic runtime for binary search.

PythonJavaC++

def binary_search(nums, target):
  left, right = 0, len(nums) - 1
  while left <= right:
      mid = left + (right - left) // 2 # ← repeated division in a loop!
      if nums[mid] == target:
          return mid
      elif nums[mid] < target:
          left = mid + 1
      else:
          right = mid - 1
  return -1

Companies That Ask Binary Search Questions

When to Use Binary Search in Interviews

Binary search is a vital tool for software engineering interviews, especially when dealing with problems involving sorted arrays or lists. The scenario of using binary search can be broken down into several categories – let's start with the usual ones before moving to the advanced uses:

Three Sum Example

Let's discuss binary search in the context of a specific problem: Three Sum.

This problem is presented as the following:

Find a unique triplet in an array that sums up to 0.

An example input and output could look like this:
Input: nums = [-1,0,1,2,-1,-4]
Output: [-1,-1,2] or [-1, 0, 1]

While it is not the most optimal solution to solve the 3Sum problem, this problem can be solved with a binary search. At first glance, it might not be immediately clear how binary search fits into this problem though! The immediate solution most people consider is a brute force and involves three nested loops trying every possible combination of 3 numbers until one results in a valid solution. However, binary search can be incredibly useful when you want to reduce the search space and increase the speed of your algorithm. The brute force is cubic O(N^3) because of the three nested loops.

After some thought, we might realize that the 3rd loop is just a linear search for a specific number. If the goal is for the three numbers to sum to zero and the first two numbers from the first two loops are -3 and -2 then we are using the 3rd and final loop to look specifically for the number 5 in the array. This is known as finding the complement of the first two numbers.

Here's the general approach for the 3Sum problem using binary search:

  1. Sort the array: This is the initial step which will facilitate the use of binary search and ensure the output triplets are not duplicates. Sorting the array will have a time complexity of O(n log n).
  2. Iterate over the array: For each index 'i' of the array, we'll try to find two other indices 'j' and 'k', such that the sum of the values at these indices equals zero. 'j' starts as the next index after 'i', and 'k' starts as the last index of the array.
  3. Binary Search: For each 'i' and 'j', we calculate the required value to reach the target as (0 - nums[i] - nums[j]). Now, we perform binary search on the array to find this value.

The sorting operation gives us a time complexity of O(n log n), the two nested loops contribute a time complexity of O(n^2), and within the innermost loop, we perform a binary search contributing a time complexity of O(log n). Thus, the overall time complexity for this solution is O(n^2 log n). Although this isn't the most efficient solution for the 3Sum problem (there's an O(n^2) solution using two pointers), it demonstrates how binary search can be applied in scenarios where it may not be immediately obvious to do so.

Advanced Binary Search

Binary Search on 2D Matrices

After you understand Binary Search on a one-dimensional array, you can explore multi-dimensional array binary search. This is a favorite type of question that Google asks. The most common multidimensional array binary search is a 2D matrix search, but there do exist three and even four dimensional search questions.

Binary Search on a Continuous Search Space

This version of binary search is used in problems where the “search space” is continuous rather than discrete. This can be useful for certain optimization problems. By continuous we mean the solutions could take on any value within a certain range, not just certain specific values. The range between 0 and 1, for instance, is infinite so finding an exact decimal in an infinite search space is tricky.

This can also apply in multidimensional continuous spaces. For example, if we are trying to find the minimum value of a continuous function, we might use a variant of binary search known as the "binary search on two points," where we divide our current range into three subranges and eliminate the subrange that has the highest function value.

Binary Search with Doubling

This is a variant of binary search where the bounds of the search are not known in advance. An initial range is established by repeatedly doubling the upper bound until it is beyond the target, then binary search is applied within the determined bounds. The key idea is to start with a small subarray size and to exponentially expand the subarray size until the subarray end exceeds the target value or the end of the full array.

Spot the Bug!

Now you might feel empowered with knowledge and new-found appreciation for the wide range of uses with binary search, but unfortunately with these problems, the biggest issue tends to be in the implementation. It is really hard to tell just by looking at your code if it is correct or not. Let's illustrate with an example – give yourself a minute and see if you can spot the error in the binary search code below!

PythonJavaC++

def binarySearch(arr, target):
  l , r = 0, len(arr)
  while l < r:
    mid = (l + r) / 2
    if arr[mid] == target:
      return mid
    if target > arr[mid]:
      l = mid
    else:
      r = mid
  return -1

Ok, did you spot the error? Trick question – depending on the language you're using and the way we count them there are actually anywhere between 4-6 errors in the above code! 🤯 Hopefully this illustrates the point that they are easy to miss! Let's walk through these errors together, one at a time.

Error 1: Right Index

PythonJavaC++

def binarySearch(arr, target):
  l , r = 0, len(arr) - 1  # <- FIXED!
  while l < r:
    mid = (l + r) / 2
    if arr[mid] == target:
      return mid
    if target > arr[mid]:
      l = mid
    else:
      r = mid
  return -1

Error 2: Conditional

Consider the edge case where we have a single element in the array which is the target that we are looking for.

arr = [5]
target = 5

l = 0
r = 0

In this test case, you'll see that both the left and right pointers end up being 0 and we skip the while loop conditional, never going inside it, and just return -1! That's wrong! Let's fix that by making the conditional <= rather than just <.

PythonJavaC++

def binarySearch(arr, target):
  l , r = 0, len(arr) - 1
  while l <= r: # <- FIXED!
    mid = (l + r) / 2
    if arr[mid] == target:
      return mid
    if target > arr[mid]:
      l = mid
    else:
      r = mid
  return -1

Error 3: Middle Index Calculation

The calculation of the middle index is incorrect. We need to find the center between the left and right pointers, but as it currently is coded we end up with a decimal number not a whole number. Since we are using this value to index into arrays, we need a whole number (there is no meaning in trying to access index 3.2 in an array, only whole indices like 3 and 4). So we need to make sure to either consistently round up or down – we recommend rounding down.

PythonJavaC++

def binarySearch(arr, target):
  l , r = 0, len(arr) - 1
  while l <= r:
    mid = (l + r) // 2 # <- FIXED!
    if arr[mid] == target:
      return mid
    if target > arr[mid]:
      l = mid
    else:
      r = mid
  return -1

Error 4: Middle Index Calculation Again

Admittedly, this next error is a bit niche, and only applies to statically typed languages like Java & C++, but it is worth knowing as a developer for historical reasons. Even after rounding down in our previous rendition this still could result in an error.

Whenever we add two large numbers together in a statically typed language we risk potentially causing an integer overflow. This error is not binary search specific, but for historical reasons it is well known for needing to be avoided in Binary Search specifically. This is due to an infamous bug in the Java library's implementation of binary search back in 2006.

PythonJavaC++

def binarySearch(arr, target):
  l , r = 0, len(arr) - 1
  while l <= r:
    mid = l + ((r - l) // 2) # <- not a problem, in python, but still a better formula
    if arr[mid] == target:
      return mid
    if target > arr[mid]:
      l = mid
    else:
      r = mid
  return -1

Error 5 & 6: Infinite Loop

Consider the edge case where we have a single element in the array (again) but it is not the target. We will enter the second if-statement, but we set the left pointer to the middle pointer and the middle pointer is 0.

arr = [2]
target = 5

l = 0
r = 0
m = 0

In this test case, all three pointers now are 0 and since our conditional checks if l <= r this will always be the case and we will loop infinitely. 😩

We don't really want to change the loop conditional because we already changed it in Error 2, to avoid a different problem so instead we can set the left and right pointers to a number less than or greater than the middle (depending on the direction).

PythonJavaC++

def binarySearch(arr, target):
  l , r = 0, len(arr) - 1
  while l <= r:
    mid = l + ((r - l) // 2)
    if arr[mid] == target:
      return mid
    if target > arr[mid]:
      l = mid + 1 # <- FIXED!
    else:
      r = mid - 1 # <- FIXED!
  return -1

Finally! A working binary search! This painful walkthrough hopefully helps illustrate a key point – binary search is extremely difficult to get right just by doing it in your head and staring at the code. Since binary search is prone to so many problems the level of scrutiny your code will be given is higher than for other problems. Be sure your binary search works!

Common Mistakes in Interviews Featuring Binary Search

Missing a Test Case

It is so easy to mess up binary search by missing a test case. This usually leads to an out-of-bounds error. This is the most common mistake in binary search questions, so take your time and test that the code works. The most common test cases that get missed are:

Holy smokes, that's a lot of tests! At interviewing.io we have found that even after interviewees know they might be missing a test case, they aren't sure which one it is and definitely don't have time to go down such an exhaustive checklist like this, so we've come up with an easy to remember acronym that will help you cover your bases. Just ask yourself, "Is my solution FINDABLE?" This reminds you to check these key edge cases to ensure your binary search solution is robust.

Forgetting Sorting Adds to the Time Complexity

Most candidates are familiar with the fact that standard comparison-based sorting takes O(N log N) time complexity, but forget to account for it in their solution. In the Three Sum question above, sorting the array takes just one line in the solution and candidates end up missing it in their overall time complexity analysis because it is so easy to skip over.

Logically Deduce Binary Search with Big-O

An advanced strategy for discovering the optimal solution to a problem is to discuss the time complexity with the interviewer. If you suggest a linear solution to a problem and try to confirm if it is optimal with the interviewer, you might get pushback on it or be told that "it's decent for now, maybe we can optimize later." This is actually a large hint towards binary search.

Discuss Edge Cases Proactively

Above we outline many edge cases for binary search. While you could go through them all in your head, you demonstrate mastery by communicating these edge cases. Checking these test cases quietly will bore your interviewer, but explaining the many test cases you are doing simultaneously shows mastery in the interview.

Binary Search Frequently Asked Questions (FAQ)

Should I Use Recursive or Iterative Binary Search?

Usually when we have the "recursive versus iterative" debate with an algorithm it is with DFS and BFS. For these algorithms it mostly doesn't matter which one you pick because you don't save any space by solving the problem iteratively versus recursively. In binary search, you don't need a stack so using recursion (and the implicit call stack) uses more space than the iterative approach. With that said, the difference between space complexities is O(1) vs O(log N). It's a small amount of space, so it doesn't really matter much from this perspective.

Why Is Binary Search Preferred Over Linear Search?

Binary search is preferred because of its time efficiency. It has a time complexity of O(log n) which makes it significantly faster than linear search (O(n)) on large datasets.

How Do You Handle Duplicates in Binary Search?

This depends on the specific requirements of the problem. If the problem is simply to find if an element exists, then any occurrence can be returned. If the problem specifies finding the first or last occurrence, then the binary search algorithm can be slightly modified to handle these cases.

Can I Use Binary Search on a Linked List?

Technically, yes, but it's not efficient. Binary search requires random access to elements, which is not possible with linked lists. Hence, using binary search on a linked list would still require O(n) time to access elements (specifically the "right pointer"), negating the benefits of using binary search in the first place.