The binary search algorithm is used in many coding problems, and it is usually not very obvious at first sight. However, there is certainly an intuition and specific conditions that may hint at using binary search. In this article, we try to develop an intuition for binary search.
Introduction to Binary Search
It is an efficient algorithm to search for a particular element, lower bound or upper bound in a sorted sequence. In case this is your first encounter with the binary search algorithm, then you may want to refer to this article before continuing: Basic Logic behind Binary Search Algorithm.
What is a Monotonic Function?
You might already know this as a mathematical concept.
- They are functions that follow a particular order.
- In mathematical terms, the function’s slope is always non-negative or non-positive.
- Monotonicity is an essential requirement to use binary search. Recall that binary search can only be applied in a sorted array [monotonic function].
E.g. a non-increasing array of numbers:
Monotonic Function
What is a Predicate Function?
They are functions that take input and return a single output TRUE or FALSE.
E.g. a function that takes an integer and returns true if the integer is greater than 0 else returns false;
Pseudocode:
bool isPositive (int input) {
if (input > 0)
return true;
else
return false;
}
Monotonic Predicate Function:
- A monotonic predicate function would look something like the following:
Monotonic Predicate Functions
- On the other hand, this function below is a predicate function but non-monotonic:
Not monotonic
- As can be observed, in a monotonic predicate function, the value can change from true to false or vice versa, a maximum of one time. It can be visualized as an array of 0’s and 1’s and check if the array is sorted in either non-increasing/ non-decreasing order.
How do Binary Search and Monotonic Predicate Functions relate?
The task is to find the first true in the given array:
Monotonic Predicate Function
Naive Approach: The naive approach traverses the array from start to end, breaks at first sight of TRUE, and returns the index.
Time Complexity: O(n)
Efficient Approach: However, the better approach is to take advantage of the fact that the array forms a monotonic function, which implies that binary search can be applied, which is better than a linear search.
Time Complexity: O(logn)
Intuition for Binary Search:
- Monotonic function appears, eg. a sorted array.
- Need to find out the minimum/maximum value for which a certain condition is satisfied/not satisfied.
- A monotonic predicate function can be formed and a point of transition is required.
Example: Chocolate Problem
Problem Statement: Given an array arr[] consisting of heights of N chocolate bars, the task is to find the maximum height at which the horizontal cut is made to all the chocolates such that the sum remaining amount of chocolate is at least K.
Examples:
Input: K = 7, arr[] = {15, 20, 8, 17}
Output: 15
Explanation: If a cut is made at height 8 the total chocolate removed is 28
and chocolate wasted is 28 – 7 = 21 units.
If a cut is made at height 15 then chocolate removed is 7
and no chocolate is wasted.
Therefore 15 is the answer.
Input: K = 12 arr[] = {30, 25, 22, 17, 20}
Output: 21
Explanation: After a cut at height 18, the chocolate removed is 25
and chocolate wastage is (25 – 12) = 13 units.
But if the cut is made at height 21 is made then 14 units of chocolate is removed
and the wastage is (14 – 12) = 2 which is the least. Hence 21 is the answer
Key Observations: Key observations related to the problem are
- Final output has to be greater than equal to 0 since that is the minimum height at which a horizontal cut can be made.
- Final output also has to be less or equal to the maximum of heights of all chocolates, since all cuts above that height will yield the same result.
- Now there is a lower and upper bound.
- Now there is a need to find the first point at which the chocolate cut out is greater than or equal to K.
- We could obviously use a linear search for this but that would be linear time complexity [O(N)].
- However, since a monotonic predicate function can be formed, we may as well use binary search, which is much better with logarithmic time complexity [O(logN)].
Approach: This can be solved using binary search as there is the presence of monotonic predicate function. Follow the steps:
- We are already getting a hint of binary search from the fact that we want the “maximum height [extreme value] for which the required sum of the remaining amount of chocolate is at least K [condition to be satisfied].”
- We can make a predicate function that takes the height of the horizontal cut and return true if the chocolate cut is greater than or equal to 7 ( k = 7 in the first example ).
See the illustration given below for better understanding
Illustration:
Take the following case as an example: K = 7, arr[] = {15, 20, 8, 17}. Initially the maximum as 20 and the minimum as 0.
- Maximum = 20, Minimum = 10: Now mid = (20+0)/2 = 10.
Cutting at a height of 10 gives, ( (15 – 10) + (20 – 10) + (0) + (17 – 10) ) = 22
Now 22 >= 7 but we need to find the maximum height at which this condition is satisfied.
So now change search space to [20, 10] both 10 and 20 include. (Note that we need to keep 10 in the search space as it could be the first true for the predicate function)
Update the minimum to 10.- Maximum = 20, Minimum = 10: Now mid = (20+10)/2 = 15.
Cutting at a height of 15 gives, ( (15 – 15) + (20 – 15) + (0) + (17 – 15) ) = 7
Now 7 >= 7 but we need to find the maximum height at which this condition is satisfied.
So now change search space to [20, 15] both 15 and 20 include.- Maximum = 20, Minimum = 15: Now new mid = (20+15)/2 = 17.
Cutting at a height of 17 gives, ( (0) + (20 – 17) + (0) + (17 – 17) ) = 3
Now 3 < 7 so we can remove 17 and all heights greater than 17 as all of them are guaranteed to be false. (Note that here we need to exclude 17 from the search space as it does not even satisfy the condition)
Now2 elements left in the search space 15 and 16.
So we can break the binary search loop where we will use the condition (high – low > 1).- Now first check if the condition is satisfied for 16, if yes then return 16, else return 15.
- Here since 16 does not satisfy the condition. Soreturn 15, which indeed is the correct answer.
Predicate Function Table
Below is the implementation of the above approach.
C++
// C++ program to implement the approach#include <bits/stdc++.h>using namespace std;// Predicate functionint isValid(int* arr, int N, int K, int height){ // Sum of chocolate cut int sum = 0; // Finding the chocolate cut // at this height for (int i = 0; i < N; i++) { if (height < arr[i]) sum += arr[i] - height; } // Return true if valid cut return (sum >= K);}int maxHeight(int* arr, int N, int K){ // High as max height int high = *max_element(arr, arr + N); // Low as min height int low = 0; // Mid element for binary search int mid; // Binary search function while (high - low > 1) { // Update mid mid = (high + low) / 2; // Update high/low if (isValid(arr, N, K, mid)) { low = mid; } else { high = mid - 1; } } // After binary search we get 2 elements // high and low which we can manually compare if (isValid(arr, N, K, high)) { return high; } else { return low; }}// Driver codeint main(){ // Defining input int arr[4] = { 15, 20, 8, 17 }; int N = 4; int K = 7; // Calling the function cout << maxHeight(arr, N, K); return 0;} |
Java
// java program to implement the approachimport java.util.Arrays;class GFG { // Predicate function static boolean isValid(int[] arr, int N, int K, int height) { // Sum of chocolate cut int sum = 0; // Finding the chocolate cut // at this height for (int i = 0; i < N; i++) { if (height < arr[i]) sum += arr[i] - height; } // Return true if valid cut return (sum >= K); } static int maxHeight(int[] arr, int N, int K) { // High as max height int[] a = arr.clone(); Arrays.sort(a); int high = a[a.length - 1]; // Low as min height int low = 0; // Mid element for binary search int mid; // Binary search function while (high - low > 1) { // Update mid mid = (high + low) / 2; // Update high/low if (isValid(arr, N, K, mid)) { low = mid; } else { high = mid - 1; } } // After binary search we get 2 elements // high and low which we can manually compare if (isValid(arr, N, K, high)) { return high; } else { return low; } } // Driver code public static void main(String[] args) { // Defining input int arr[] = { 15, 20, 8, 17 }; int N = 4; int K = 7; // Calling the function System.out.println(maxHeight(arr, N, K)); }}// This code is contributed by saurabh_jaiswal. |
Python3
# Python code for the above approach# Predicate functiondef isValid(arr, N, K, height): # Sum of chocolate cut sum = 0 # Finding the chocolate cut # at this height for i in range(N): if (height < arr[i]): sum += arr[i] - height # Return true if valid cut return (sum >= K)def maxHeight(arr, N, K): # High as max height high = max(arr) # Low as min height low = 0 # Mid element for binary search mid = None # Binary search function while (high - low > 1): # Update mid mid = (high + low) // 2 # Update high/low if (isValid(arr, N, K, mid)): low = mid else: high = mid - 1 # After binary search we get 2 elements # high and low which we can manually compare if (isValid(arr, N, K, high)): return high else: return low# Driver code# Defining inputarr = [15, 20, 8, 17]N = 4K = 7# Calling the functionprint(maxHeight(arr, N, K))# This code is contributed by Saurabh Jaiswal |
C#
// C# program to implement the approachusing System;public class GFG { // Predicate function static bool isValid(int[] arr, int N, int K, int height) { // Sum of chocolate cut int sum = 0; // Finding the chocolate cut // at this height for (int i = 0; i < N; i++) { if (height < arr[i]) sum += arr[i] - height; } // Return true if valid cut return (sum >= K); } static int maxHeight(int[] arr, int N, int K) { // High as max height int[] a = new int[arr.Length]; a =arr; Array.Sort(a); int high = a[a.Length - 1]; // Low as min height int low = 0; // Mid element for binary search int mid; // Binary search function while (high - low > 1) { // Update mid mid = (high + low) / 2; // Update high/low if (isValid(arr, N, K, mid)) { low = mid; } else { high = mid - 1; } } // After binary search we get 2 elements // high and low which we can manually compare if (isValid(arr, N, K, high)) { return high; } else { return low; } } // Driver code public static void Main(String[] args) { // Defining input int []arr = { 15, 20, 8, 17 }; int N = 4; int K = 7; // Calling the function Console.WriteLine(maxHeight(arr, N, K)); }}// This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript code for the above approach // Predicate function function isValid(arr, N, K, height) { // Sum of chocolate cut let sum = 0; // Finding the chocolate cut // at this height for (let i = 0; i < N; i++) { if (height < arr[i]) sum += arr[i] - height; } // Return true if valid cut return (sum >= K); } function maxHeight(arr, N, K) { // High as max height let high = Math.max(...arr); // Low as min height let low = 0; // Mid element for binary search let mid; // Binary search function while (high - low > 1) { // Update mid mid = Math.floor((high + low) / 2); // Update high/low if (isValid(arr, N, K, mid)) { low = mid; } else { high = mid - 1; } } // After binary search we get 2 elements // high and low which we can manually compare if (isValid(arr, N, K, high)) { return high; } else { return low; } } // Driver code // Defining input let arr = [15, 20, 8, 17] let N = 4; let K = 7; // Calling the function document.write(maxHeight(arr, N, K)); // This code is contributed by Potta Lokesh </script> |
15
Time Complexity: O(N*logN)
Auxiliary Space: O(1)
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
