We all know that Binary search is the most efficient search algorithm as of now, and it has multiple applications in the programming domain for the same reason. But very often the problems do not have any information about applying Binary Search or even any hint on using a Searching algorithm altogether. So it becomes very important to have an understanding of how to identify Binary Search Problems, how to solve Binary Search problems and what are the most common interview questions that have a Binary Search solution involved. In this post, we have curated the topics to do just that.
Table of Content
- What is the Binary Search Technique?
- Possible Cases of problems and in which Case binary search can be applied or not:
- How to Identify Binary Search Problems?
- How to Solve Binary Search Problems?
- Example to show How to Identify & Solve a Problem using Binary search:
- Most Common Interview Problems on Binary Search
What is the Binary Search Technique?
Binary search is a searching technique to search an ordered list of data based on the Divide and Conquer technique which repeatedly divides the search space by half in every iteration.
Possible types of problems and in which type Binary Search can be applied or not:
1) When Input is sorted:
In this case, Identification as a binary search problem is very straightforward as we can easily deduce which half needs to be removed from the search space.
2)When Input is unsorted but the problem follows a monotonic nature:
In this case also binary search can be applied as the problem follows a monotonic nature which means the function can be either increasing or decreasing with an increase in a parameter so that one-half can be removed from search space.
3)When the Expected answer is ordered:
Whenever we can identify that the answer to the problem lies between in a range L to R and there is a Monotonic Behaviour of the answer in range L to R then we can think to apply binary search on the answer.
4)When Neither input is sorted nor the problem follows monotonic behavior:
In this case we can not apply binary search.
Identify and Solve Binary Search Problems
Now here is the general technique to Identify and Solve the Binary search problems.
How to Identify Binary Search Problems?
Based on the number of problems involving Binary Search, we can safely assume the scenario when Binary search is involved in a problem, as mentioned below:
Binary search can only be applied to a problem if and only if the Problem is monotonic in nature.
When a Problem is considered to be Monotonic?
Suppose we are given a problem f() and the expected solution to this problem is y, then we can define the problem as
y = f(n)
Now if this problem show a behaviour such that it either only increases or only decreases with the change in parameter. Then it is said that the problem shows Monotonic (only single direction) behaviour.
In other words, A function f(n1) is said to be monotonic if and only if:
- for any n1, if f(n1) returns true, then for any value of n2 (where n2 > n1), f(n2) should also return true,
- and similarly, if for a certain value of n1 for which f(n1) is false, then for any value n2 (n2 < n1) the function f(n2) should also return false.
The same is shown in the graph below:
Monotonic Functions
Now if this problem shows a monotonic behavior, generally this tells you that you can apply a binary search here.
How to Solve Binary Search Problems?
- Define a search space by pointers let’s say low to high.
- Calculate mid value of search space,and check mid value is true or false.
- Considering above resut figure out where expected answer should lie, In the left half or right half Then update the search space accordingly.
- Repeat the above steps till there is search space left to search.
Example to show How to Identify & Solve a Problem using Binary search:
Problem Statement : Given an array arr[] of integers and a number x, the task is to find the minimum length of subarray with a sum greater than the given value k.
Example:
Input: arr[] = {1, 4, 45, 6, 0, 19}, x = 51
Output: 3
Explanation:Minimum length subarray is {4, 45, 6}
Identification as a Binary Search Problem:
Let n1 is size of subarray and f(n1) is true i.e. there is a subarray of size n1 whose sum is greater than x.
Take any n2 (n2>n1) i.e at least one more element than previous subarray size then it is guaranteed that f(n2) must hold true because there is subarray of size n1 has sum greater than x, adding at least one non-negative integer increases the sum.
Problem is monotonic in nature and can be solved using binary search.
Solution of the Problem using Binary search:
- Define search space
- low = 0,as minimum size of subarray can be zero.
- high = length of the array, as subarray size can be up to length of array.
- Calculate mid value as (low+high)/2 and check f(mid) returns true or false.
- Check sum of every subarray of size mid is greater than x or not using sliding window.
- if there is a subarray present then f(mid) is true.
- else f(mid) is false.
- Check sum of every subarray of size mid is greater than x or not using sliding window.
- Update the search space:
- if f(mid) is true and minimal length to be find then expected answer should lie in left half (high = mid-1) as in the right half of mid all the value are true, store the mid value as best possible answer till now.
- if f(mid) is false i.e. there is no subarray of size mid,so size need to be increased to increase the sum.Means expected answer should lie in the right half(low =mid+1).
- Repeat the above steps with updated search space till there is search space to search.
Implementation of the above solution:
C++
#include <bits/stdc++.h>;using namespace std;bool f(int mid, int arr[], int n, int x){ // var to store is there any subarray present or not bool issubarray = false; int i = 0, j = 0, sum = 0; for (j = 0; j < mid; j++) { sum += arr[j]; } // slide window of mid size and check if sum is greater // than x or not while (j < n) { // if sum > x then there exist a subarray of size // mid if (sum > x) { issubarray = true; } sum -= arr[i]; sum += arr[j]; i++; j++; } if (sum > x) { issubarray = true; } return issubarray;}// Function to calculate the smallest subarray size whose// sum is less than xint smallestSubWithSum(int arr[], int n, int x){ // defining search space from low to high and ans to // store the minimum subarray size int low = 0, high = n, ans = INT_MAX; while (low <= high) { // calculating mid int mid = (low + high) / 2; // check if there exist a subarray of size mid whose // sum is greater than x if (f(mid, arr, n, x)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } // return the minimal length return (ans == INT_MAX) ? 0 : ans;}// Driver codeint main(){ int arr[] = { 1, 4, 45, 6, 0, 19 }; int n = 6; int x = 51; cout << smallestSubWithSum(arr, n, x); return 0;} |
Java
// Java Implementationpublic class SmallestSubarray { // Function to check if there exists a subarray of size mid // whose sum is greater than x static boolean isSubarrayPresent(int mid, int[] arr, int n, int x) { // Variable to store if there is any subarray present or not boolean isSubarray = false; int i = 0, j = 0, sum = 0; // Calculate the sum of the first 'mid' elements for (j = 0; j < mid; j++) { sum += arr[j]; } // Slide the window of size 'mid' and check if the sum is greater than x or not while (j < n) { // If sum > x, then there exists a subarray of size mid if (sum > x) { isSubarray = true; } // Adjust the sum by removing the first element and adding the next element sum -= arr[i]; sum += arr[j]; i++; j++; } // Check one last time if the sum is greater than x if (sum > x) { isSubarray = true; } return isSubarray; } // Function to calculate the smallest subarray size whose // sum is less than x static int smallestSubarrayWithSum(int[] arr, int n, int x) { // Define the search space from low to high and ans to // store the minimum subarray size int low = 0, high = n, ans = Integer.MAX_VALUE; while (low <= high) { // Calculate mid int mid = (low + high) / 2; // Check if there exists a subarray of size mid whose // sum is greater than x if (isSubarrayPresent(mid, arr, n, x)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } // Return the minimal length return (ans == Integer.MAX_VALUE) ? 0 : ans; } // Driver code public static void main(String[] args) { int[] arr = { 1, 4, 45, 6, 0, 19 }; int n = 6; int x = 51; System.out.println(smallestSubarrayWithSum(arr, n, x)); }}// This code is contributed by Tapesh(tapeshdua420) |
Python3
def f(mid, arr, n, x): # Initialize variables is_subarray = False i, j, summation = 0, 0, 0 # Calculate initial sum of the subarray of size 'mid' for j in range(mid): summation += arr[j] # Sliding window approach to find subarrays whose sum exceeds 'x' while j < n: if summation > x: is_subarray = True # Set flag if sum exceeds 'x' summation -= arr[i] # Update sum by removing arr[i] summation += arr[j] # Update sum by adding arr[j] i += 1 # Move window start pointer j += 1 # Move window end pointer if summation > x: is_subarray = True # Check the last subarray before exiting return is_subarraydef smallestSubWithSum(arr, n, x): low, high, ans = 0, n, float('inf') # Binary search to find the smallest subarray whose sum is less than 'x' while low <= high: mid = (low + high) // 2 # Check if there exists a subarray of size 'mid' whose sum exceeds 'x' if f(mid, arr, n, x): ans = mid # Update answer to current mid high = mid - 1 # Reduce search space to the left else: low = mid + 1 # Move to the right in the search space return ans if ans != float('inf') else 0 # Return the smallest subarray size or 0 if not found# Driver codearr = [1, 4, 45, 6, 0, 19]n = 6x = 51print(smallestSubWithSum(arr, n, x)) # Output the result of smallest subarray sum less than 'x' |
Javascript
function f(mid, arr, n, x) { // Variable to store whether there is any subarray present or not let issubarray = false; let i = 0, j = 0, sum = 0; // Calculate the initial sum for the first 'mid' elements for (j = 0; j < mid; j++) { sum += arr[j]; } // Slide the window of size 'mid' and check if the sum is greater than x while (j < n) { // If sum > x, then there exists a subarray of size 'mid' if (sum > x) { issubarray = true; } // Adjust the sum for the sliding window sum -= arr[i]; sum += arr[j]; i++; j++; } // Check the sum for the last window if (sum > x) { issubarray = true; } return issubarray;}// Function to calculate the smallest subarray size whose sum is less than xfunction smallestSubWithSum(arr, n, x) { // Define the search space from low to high and ans to store the minimum subarray size let low = 0, high = n, ans = Number.MAX_SAFE_INTEGER; // Binary search to find the smallest subarray size while (low <= high) { // Calculate mid let mid = Math.floor((low + high) / 2); // Check if there exists a subarray of size 'mid' whose sum is greater than x if (f(mid, arr, n, x)) { ans = mid; high = mid - 1; } else { low = mid + 1; } } // Return the minimal length return (ans === Number.MAX_SAFE_INTEGER) ? 0 : ans;}// Driver codelet arr = [1, 4, 45, 6, 0, 19];let n = 6;let x = 51;console.log(smallestSubWithSum(arr, n, x)); |
3
Time Complexity:O(NlogN),N is the size of the subarray
Auxiliary space: O(1)
Most Common Interview Problems on Binary Search
|
Problem Name |
Practice Link to the Problem |
|---|---|
|
Binary Search |
|
|
Floor in a Sorted Array |
|
|
First and last occurrences of X |
|
|
Peak element |
|
|
Square root of a number |
|
|
Koko Eating Bananas |
|
|
Minimum days to make M bouquets |
|
|
Smallest Divisor |
|
|
Capacity To Ship Packages Within D Days |
|
|
Aggressive Cows |
|
|
Allocate minimum number of pages |
|
|
Median of 2 Sorted Arrays of Different Sizes |
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
