I have written many posts on binary search algorithm and there are plenty of problems and their variations which can be solved using binary search algorithm. This post is collection of all such problems and their solutions. Please search this blog to read detailed explanation of each of the problem if you want.
First of all let’s understand what is binary search algorithm. Algorithm is very easy, split the array into two halves and based on the value of mid either look for the key in left part or left part. Since every time input space is reduced to half and same processing needs to be done on two halves, recursion is best way to implement it. However, it is good to mention that recursive implementation may not work in production environment where stack overflow may happen due to depth of recursion. So, in production environments, it is advisable to use iterative version of algorithm.
Binary search algorithm
Recursive implementation of binary search algorithm
If you analyze the algorithm, it’s not that difficult; all we do is that based on key we are looking for, discard half of the array. For recursion specially, there needs to be base case. In binary search, base condition is when you can not divide the array further. When does that happen? When there is only element in array. Just check if that one element is equal to what we are looking for, if yes, great. If not, then return null or some sentinel value. In implementation above, this base is when start and end of input array are same.
Let’s see some of the problem being solved using binary search algorithm.
1. Find first instance of a number in sorted array where duplicates are allowed.
This is typical problem where binary search algorithm can be easily extended to arrive at solution. In standard BSA, we exit as soon as mid is equals to the key being searched, where as in this case, once mid element matches the key, that element is a candidate for solution. However, same number may exists prior to mid too as duplicates are allowed. Since find first instance to be found, safely discard all elements on right side of the mid, but still need to check on left side of mid for first instance. So, again repeat the binary search on left subarray. Only change here is : termination condition. One is when there is one element in array when we exit anyways; second exit condition is when element at index mid is equal to key and mid-1 is not equal to key.
2. Find last instance of a number in sorted array if duplicates are allowed.
Same explanation as above. Only two things change. We have to discard left part of array when mid equals to key and exist when mid + 1 element is not equal to mid element.
3. Find number of instances of a number in sorted array when duplicates are allowed.
To find numbers instances just find the first instance and last instance of occurrence and then return last-first + 1.
4. Find minimum element in rotated sorted array or Find number of times array is rotated.
Explanation of this problem can be found at : Find minimum element in sorted rotated array
5. Find a number in rotated sorted array.
Explanation of problem and solution can be found here : Find element in sorted rotated array
6. Find a point where arrays starts decreasing, array is first increasing and then decreasing.
Please share if you have some other problems which can be solved with slight modification of binary search algorithm.