 Photo by Joanna Kosinska on Unsplash

Binary search, as we all know, is the easiest difficult algorithm to get right.

It is also one of the smartest searching algorithms with a guaranteed running time of O(logN) for an input array containing N elements.

In this post, I will share three smart modifications of the binary search algorithm that will help you solve dozens of coding problems. I will share a few of these problems in this post too.

Whenever we encounter a sorted Array, List, or Matrix in a coding problem and we are asked to find a specific number, we all know that the best algorithm we can use is the binary search.

Here are a few examples of such problems:

1. Given an array of numbers, sorted in ascending order. Find the ceiling of a given number “key”. The ceiling of the key will be the smallest element in the given array, greater than or equal to the key.
2. Given an array of lowercase letters sorted in ascending order. Find the smallest letter in the given array, greater than a given key.
3. Given an array of numbers sorted in ascending order. Find the element in the array that has the minimum difference with the given key.

It is straightforward to realize that all the above problems can be solved with a few modifications to the basic binary search algorithm. (Solutions can be found in Grokking the Coding Interview).

However, with some problems, it is not easy to understand that we can utilize binary search, especially when the given input is not an array (such as a Matrix or a List whose length we don’t know).

The three approaches that we will discuss in this post will try to explain how we can use binary search for different data structures and problem constraints.

We will name these approaches:

1. Order-agnostic binary search
2. Searching in an infinite List
3. Searching in a sorted Matrix

Let’s understand these approaches with real coding problems.

Approach 1: Order-Agnostic Binary Search

Problem statement

Given a sorted array of numbers, find out if a given number key is present in the array.

Though we know that the array is sorted, we don’t know if it’s sorted in ascending or descending order. You should assume that the array can have duplicates.

Write a function to return the index of the key if it is present in the array, otherwise return -1.

Example-1: Input: [1, 2, 3, 4, 5, 6, 7], key = 5, Output: 4Example-2: Input: [10, 6, 4], key = 10, Output: 0

Solution

To make things simple, let’s first solve this problem assuming that the input array is sorted in ascending order.

These are the steps for binary search:

Step 1

Let’s assume start points to the first index and end points to the last index of the input array (let’s call it arr). This means: int start = 0; int end = arr.length — 1;

Step 2

First, we will find the middle of start and end.

An easy way to find the middle would be: middle=(start+end)/2.

For Java and C++, this equation will work most of the time, but when start or end is large, this equation will give us the wrong result due to integer overflow.

Imagine that start is equal to the maximum range of an integer (e.g. for Java: int start = Integer.MAX_VALUE). Now, adding anything to start will result in an integer overflow. As we need to add both numbers first to evaluate our equation, an overflow might occur.

The safest way to find the middle of two numbers without getting an overflow is as follows: middle = start + (end-start)/2.

The above discussion is not relevant to Python, as we don’t have the integer overflow problem in pure Python.

Step 3

Next, we will see if the key is equal to the number at the index middle. If it is equal, we return middle as the required index.

Step 4

If the key is not equal to the number at the index middle, we have to check two things:

• If key < arr[middle], then we can conclude that the key will be smaller than all the numbers after the index middle, as the array is sorted in ascending order. Hence, we can reduce our search to end = mid - 1.
• If key > arr[middle], then we can conclude that the key will be greater than all numbers before the index middle, as the array is sorted in ascending order. Hence, we can reduce our search to start = mid + 1.

Step 5

We will repeat steps 2 to 4 with new ranges of start to end.

If at any time, start becomes greater than end, this means that we can’t find the key in the input array and we must return -1.

Here is the visual representation of binary search for the first example:

If the array is sorted in descending order, we have to update step 4 above, because:

• If key > arr[middle], then we can conclude that the key will be greater than all the numbers after the index middle, as the array is sorted in descending order. Hence, we can reduce our search to end = mid - 1.
• If key < arr[middle], then we can conclude that the key will be smaller than all the numbers before the index middle, as the array is sorted in descending order. Hence, we can reduce our search to start = mid + 1.

Finally, how can we figure out the sort order of the input array?

We can compare the numbers pointed out by the start and end indexes to find the sort order. If arr[start] < arr[end], it means that the numbers are sorted in ascending order, otherwise they are sorted in descending order.

Code

Here is the Java code to solve this problem:

Time and space complexity

As we are reducing the search range by half at every step, it means that the time complexity of our algorithm will be O(logN) where N is the total number of elements in the given array.

The algorithm runs in constant space O(1).

Approach 2: Searching in an Infinite List

Problem statement

Given an infinite sorted array (or an array with unknown size), find out if a given number key is present in the array.

Write a function to return the index of the key if it is present in the array, otherwise return -1.

As it is not possible to define an array with infinite (unknown) size, you will be provided with an interface ArrayReader to read elements of the array.

ArrayReader.get(index) will return the number at the index; if the array’s size is smaller than the index, it will return Integer.MAX_VALUE.

Example: Input: [4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30], key = 16
Output: 6., Explanation: The key is present at index ‘6’ in the array.

Solution

As binary search helps us find a number in a sorted array efficiently, we can use a modified version of the binary search to find the key in an infinite sorted array.

The only issue with applying Binary Search to this problem is that we don’t know the bounds of the array. To handle this situation, we will first find the proper bounds of the array where we can perform a binary search.

An efficient way to find the proper bounds is to start at the beginning of the array with the bound’s size as 1 and exponentially increase the bound’s size (i.e., double it) until we find the bounds that can have the key.

Consider the example mentioned above:

Once we have searchable bounds, we can apply the binary search.

Code

Here is the Java code to solve this problem:

Time and space complexity

There are two parts of the algorithm.

In the first part, we keep increasing the bound’s size exponentially (double it every time) while searching for the proper bounds. Therefore, this step will take O(logN) assuming that the array will have maximum N numbers.

In the second step, we perform the binary search, which will take O(logN), so the overall time complexity of our algorithm will be O(logN + logN) which is asymptotically equivalent to O(logN).

The algorithm runs in constant space O(1).

Approach 3: K-th Smallest Number in a Sorted Matrix

Problem statement

Given an N * N matrix where each row and column is sorted in ascending order, find the K-th smallest element in the matrix.

Solution

As each row and column of the matrix is sorted, is it possible to use binary search to find the K-th smallest number?

The biggest problem using binary search, in this case, is that we don’t have a straightforward sorted array, instead, we have a matrix.

As we remember, in binary search, we calculate the middle index of the search space (1 to N) and see if our required number is pointed out by the middle index. If not, we either search in the lower half or the upper half.

In a sorted matrix, we can’t really find a middle. Even if we do consider some index as middle, it is not straightforward to find the search space containing numbers bigger or smaller than the number pointed out by the middle index.

An alternative could be to apply the binary search on the “number range” instead of the “index range”.

As we know, the smallest number of our matrix is at the top left corner and the biggest number is at the bottom lower corner. These two numbers can represent the range, i.e., the start and the end for the binary search.

Here is how our algorithm will work:

1. Start the binary search with start = matrix and end = matrix[n-1][n-1].
2. Find the middle of the start and the end. This middle number is not necessarily an element in the matrix.
3. Count all the numbers smaller than or equal to middle in the matrix. As the matrix is sorted, we can do this in O(N).
4. While counting, we can keep track of the “smallest number greater than the middle” (let’s call it n1) and, at the same time, the “biggest number less than or equal to the middle” (let’s call it n2). These two numbers will be used to adjust the number range for the binary search in the next iteration.
5. If the count is equal to K, n1 will be our required number as it is the “biggest number less than or equal to the middle”, and is definitely present in the matrix.
6. If the count is less than K, we can update start = n2 to search in the higher part of the matrix and if the count is greater than K, we can update end = n1 to search in the lower part of the matrix in the next iteration.

Here is the visual representation of our algorithm:

Code

Here is the Java code to solve this problem:

Time and space complexity

The binary search could take O(log(max−min)) iterations where max is the largest and min is the smallest element in the matrix, and in each iteration, we take O(N) for counting.

Therefore, the overall time complexity of the algorithm will be O(N∗log(max−min)). The algorithm runs in constant space O(1).

Conclusion

The three approaches for using binary search, discussed in this post, have helped me solve a lot of coding problems and also helped me to apply binary search to different data structures, like Matrix and Lists.

Take a look at Grokking the Coding Interview for more coding questions and solutions using these techniques.