How to identify a Binary Search problem?
If you don’t know what’s binary search, please refer my article on Binary Search.
Binary Search is one of the most asked topics in interviews by big companies. You must be thinking why would big companies ask to search an element in an array? Well, they focus on implementation of algorithms. They want you to identify how an algorithm can be used in a problem.
There are a plenty of problems which can be solved by implementing Binary Search, but we have to identify such problems. We need to train our brain to focus on keywords. If it says sorted array, this means binary search can be applied in some manner. Following is a list of problems which will help you identify Binary Search implementation :-
I. Order Agnostic Search :
An order agnostic search problem doesn’t specify the order in which the array is sorted. It may be in ascending order or in descending order. So first identify the order and then apply binary search accordingly.
II. Find the range of occurrence of an element in a sorted array :
By finding the range of an element, it actually wants us to identify the first and last occurrence of that element in the array of size n. This is nothing but searching of an element in an array. Since the array is sorted, we’ll use binary search.
Let’s begin with the basic idea behind Binary Search Algorithm. We need to divide our problem in two halves and discard one of them. Its quite evident that if we find an element at the middle of the array, then the possibility of finding its first occurrence is towards left and possibility of finding its last occurrence is towards right. So we need to move to extreme left and extreme right while we keep finding the element.
III. Frequency of an element in a sorted array :
A sorted array can have duplicate values as well. So we need to count the number of times a particular element has occurred. Since we have found the first and last occurrence of an element, we can easily find out the frequency using the formula - (last occurrence index - first occurrence index + 1).
IV. Find the number of times a sorted array is rotated :
If we take a closer look to this array, we notice that the number of rotations is actually the index of the minimum element. So we need to find out the minimum element. We can do that in O(n) using Linear Search Algorithm and in O(log n) using Binary Search Algorithm.
Its evident that the minimum element will be the one whose previous element is greater than it. If there is no previous element, that means there is no rotation. We can check this condition for middle element by comparing it with (mid - 1)’th and (mid + 1)’th elements.
If the minimum element is not at the middle (neither mid nor mid + 1), then minimum element lies in either left half or right half.
- If middle element is smaller than last element, then the minimum element lies in left half
- Else minimum element lies in right half.
V. Find an element in a rotated sorted array :
The problem discussed above tells us what a rotated sorted array is. Now we need to find an element in that array. The basic idea here is to find the inflection point, divide the array in two sub-arrays and call binary search.
The main idea to find inflection point for a sorted (in increasing order) and rotated array is that inflection point is the only element for which next element to it is smaller than it.
After finding inflection point, we know the left and right half is sorted. So now we can apply binary search in the two halves and finally return the maximum of these as one of the two halves will not find the element and return -1.
Using above criteria and Binary Search Algorithm we can get inflection point in O(log n) time.
VI. Searching in a nearly sorted array :
A nearly sorted array is an array in which an element that was supposed to be at position ‘i’, can be at positions ‘i’, ‘i - 1’ or ‘i + 1’.
This problem can obviously be solved using Linear Search in O(n) time but we can take the advantage of the fact that array is nearly sorted. There can be a way in which Binary Search can be used here.
In binary search, usually we compare the key with the middle element, but here we’ll compare it with 3 middle values i.e. mid, (mid - 1) and (mid + 1). If we find a match, then return the index otherwise divide the array in two halves and decide which one is to be traversed now.
If the key is lesser than the value at mid, then we need to go to left i.e. end = mid - 2, otherwise we need to go to right i.e. start = mid + 2
VII. Find floor of an element in a sorted array
Floor: Largest element smaller than or equal to the key
To find floor of the key, we can again use binary search. First compare at mid, if match found, that’s the answer otherwise if key is smaller than the value at mid, move left else store ans = mid and move right.
VIII. Find ceil of an element in a sorted array
Ceil: Smallest element greater than or equal to the key
To find ceil of the key, we can again use binary search. First compare at mid, if match found, that’s the answer otherwise if key is greater than the value at mid, move right else store ans = mid and move left.
IX. Find next smallest alphabet to a given alphabet
Its a similar problem as finding ceil of an element. We have to find smallest next element to the given letter but not the equal letter.
X. Find position of an element in an infinite sorted array
This is a problem which may be asked in an interview but you won’t be asked to code it down because taking an input of an infinite array is unrealistic.
Since the array is infinite, you know where to start but you don’t know where’s the end. So for simplicity, we’ll assume first element to be the start and second element to be the end. Now, while the key is greater than value at end, start = end and end = 2 * end. As the loop ends, we’ll have the actual range in start and end, so we can now do normal binary search in this range.
XI. Find the index of first ‘1’ in an infinite binary sorted array
An infinite binary sorted array will consist of only 0’s and 1’s such that all 0’s occur before all 1’s. Now, we need to find out the first occurrence of ‘1’ in this array.
This problem is a combination of two problems :
- Searching in an infinite sorted array
- Finding first occurrence of the key
Using approaches of above two problems, this problem can be solved easily in O(log n).
XII. Find minimum difference element in a sorted array
In this problem, we need to find an element which has minimum difference with the given key.
If key is present in the array, then without any doubt, that element will be our answer otherwise, either the floor or ceil of the key will be our answer.
So, compare with the element at mid, if match found, return mid otherwise, find floor (will point to start) and ceil (will point to end) of the key. Finally, minimum of (element at start - key) and (element at end - key) will be the answer.
XIII. Binary search on answer
This method can be applied on an unsorted array as well.
For example, finding the peak element i.e. an element which is greater than both its neighbors.
Check for the peak at mid i.e. element at mid should be greater than element at (mid - 1) and (mid + 1). If yes, we’ve found the peak otherwise, check if element at (mid + 1) is greater than element at mid, if yes, move right else check if element at (mid -1) is greater than element at mid, if yes, move left.
In this way, we can find the peak element in O(log n).
XIV. Find maximum element in a bitonic array
Bitonic Array: A bitonic array has monotonically increasing elements and then monotonically decreasing elements.
This is nothing but the same problem as discussed above. We need to find that peak element again.
XV. Searching in a bitonic array
This is a similar problem to searching in a rotated sorted array but not the same.
Here first we need to find the index of the peak element. Now, all the elements to the left of peak index will be sorted in increasing order and all the elements to the right of peak index will be sorted in decreasing order.
So, now we can apply usual binary search in both the halves.
XVI. Searching in a row wise and column wise sorted array
Even if its a 2D matrix, we can still apply binary search here to search an element.
We’ll start from the top right corner i.e. last element in first row. If the element matches the key, then return cell indexes otherwise, if the element is greater than key, we need to move left i.e. decrement column value else we need to move downwards i.e. increment row value.
Please find few more problems here.
I hope this article was useful for you. I’ve listed some key problems of Binary Search Algorithm but there can be various other problems but similar to these. I hope you all can identify a Binary Search problem now.
All the best peeps! Keep coding! ❤
