When to use Binary Search ?
Binary search can be applied to any problem that can be expressed as
a search problem over a monotonic function. This means that if you can find
a way to represent your problem as a monotonic function, then you can use binary
search to solve it.
| Monotonic Function | Can Binary Search be Applied? |
|---|---|
| Monotonically increasing | True |
| Monotonically decreasing | True |
| Piecewise monotonic | True |
| Sorted array | True(As it is monotonic fn) |
| Non-monotonic | False |
Here is a table i have shown the problems that can be solved using binary search
and how they are monotonic:
| Problem | Monotonic Function |
|---|---|
| Finding the minimum or maximum value of a function | The function is monotonically increasing or decreasing |
| Finding the root of a number | The function is monotonically increasing or decreasing |
| Finding the smallest or largest element in a range | The function is monotonically increasing or decreasing |
| Finding the number of times a function crosses a given value | The function is piecewise monotonic |
| Finding the first occurrence of a value in a sorted array | The array is sorted, so the function is monotonically increasing |
| Finding the last occurrence of a value in a sorted array | The array is sorted, so the function is monotonically decreasing |
A monotonic function is a function whose value either always increases or
always decreases. This means that the function's value will always be greater than
or equal to its previous value, or always less than or equal to its previous value.
(Image from statisticshowto.com)
A monotonically increasing function is a function whose value always increases as the input increases.
A monotonically decreasing function is a function whose value always decreases as the input increases.
A piecewise monotonic function is a function that is monotonic over some intervals, but not monotonic over other intervals.
Why to use Binary Search ?
Binary search is a divide-and-conquer algorithm. This means that it works by
recursively dividing the search space in half until the desired value is found.
The time complexity of binary search is O(log n), where n is the number of elements
in the array. This means that the number of comparisons required to find the desired
value grows logarithmically as the size of the array grows
To understand how binary search works, imagine you are looking for a specific word
in a dictionary. You could start by opening the dictionary to the middle page and
looking for the word there. If the word is on that page,** you're done.**
If the word is not on that page, you can then narrow down your search to either
the first half of the dictionary or the second half of the dictionary.
You can continue to narrow down your search in this way until you find the word or
until you have searched the entire dictionary.
Binary search works in a similar way. It starts by looking at the middle element of
a sorted array. If the element is the value you are looking for, then binary search
terminates. If the element is not the value you are looking for, then binary search
narrows down its search to either the first half or the second half of the array,
depending on whether the value you are looking for is less than or greater than the
middle element. Binary search continues to narrow down its search in this way until
it finds the value you are looking for or until it has searched the entire array.
The main idea behind binary search is that it can reduce the size of the search space
by half at each step. This means that the number of steps required to find the value
you are looking for is logarithmic in the size of the array. For example, if the array
contains 100 elements, then binary search will only require 7 steps to find the value you
are looking for.
In contrast, a linear search would require 100 steps to find the value you are looking
for in this case. This is because a linear search would have to look at every element
in the array before it could find the value you are looking for.
The reason why binary search is so efficient is because it can take advantage
of the fact that the elements in the array are sorted. This allows binary search
to quickly narrow down its search space and find the value you are looking for.
int binary_search(vector<int> &v, int target)
{
int l = 0, h = v.size() - 1, ans = -1;
while (l <= h)
{
int mid = (l + h) / 2;
if (v[mid] == target)
return ans = mid;
else if (v[mid] < target)
l = mid + 1;
else
h = mid - 1;
}
return ans;
There are two cases available for mid = start + end/2 and mid = start + (end-start)/2:
The expression mid = start + (end - start) / 2 is generally preferred over mid = start + end / 2 because it avoids overflow errors. However, I won't go into detail here. If you're doing binary search, you should be aware of overflow errors. Otherwise, you can read my article on bits, where I discuss overflow in detai
}How to save yourself from infinite loop in binary search
The binary search algorithm works by repeatedly dividing the search space
in half and then checking if the target value is in the smaller half.
This process is repeated until the target value is found or until the
search space is empty.
An infinite loop can occur in binary search if the search space is never empty,
even though the target value is not in the array. This can happen if
the low and high pointers are always equal to the mid pointer.
To avoid an infinite loop, you should never set low or high to mid.
Instead, you should always update low or high to the next smaller or larger index,
respectively. This will ensure that the search space is always shrinking, and the
loop will eventually terminate
In my code, I am are storing the answer in a temporary variable,
and then updating low or high based on the result of the comparison
and ensure that the search space is always shrinking.
eg->
// lower bound
int lowerbound(vector<int> &nums, int target)
{
int l = 0, h = nums.size() - 1, ans = -1;
while (l <= h)
{
int mid = l + (h - l) / 2;
if (nums[mid] >= target)
{
ans = mid; // A possible answer and try to find
// first occurrence of element if equal to target else first element greater than target
h = mid - 1;
}
else
l = mid + 1;
}
return ans;
}eg->
// upper bound
int upperbound(vector<int> nums, int target)
{
int l = 0, h = nums.size() - 1, mid = 0, ans = -1;
while (h>=l)
{
mid = (l + h) / 2;
if (nums[mid] > target)
{
ans = mid; // A possible answer and try to find lowest possible number
// greater than target
h=mid-1;
}
else
l = mid+1;
}
return ans;
} How to handle binary Seach when not possible to shrink search space ?
- How magical is Binary search ?
In some cases, the binary search algorithm may not be able to shrink the search space
at all. This can happen if the target value is not in the array, or if the array is
sorted in reverse order In this case, the algorithm will simply loop until it has
iterated 100 times.
The reason why the algorithm loops 100 times is because the binary search algorithm
has a worst-case time complexity of O(log n), where n is the size of the array.
This means that the algorithm will never take more than log n steps to terminate,
even in the worst case. So, even if the target value is not in the array,
the algorithm will still terminate after 100 loops, at most.
The reason why we choose 100 is because it is a relatively small number that is still large enough to cover most possible constraints. For example, the logarithm of 10^25 is roughly equal to 75,
so 100 will cover almost all possible arrays with a size of 10^25 or if 100 will not work you can increase 100 to more according to your constaint
eg->Square Root
class Solution {
public:
int mySqrt(int n) {
double left = 0, right = n, mid = 0;
for (int i = 0; i < 100; i++)
{
mid = (left + right) / 2;
if (mid * mid > n)
right = mid;
else if (mid * mid <= n)
left = mid;
}
return mid;
}
// square root of an integer can be a decimal number
// For example, the square root of 3 is 1.732 that's why i used double
};Binary search where you have to write Monotonic function()
Lets understand how to think using this example
koko-eating-bananas
The problem is to find the minimum integer k such that Koko can eat all the
bananas within h hours. The search space is the range of k values that Koko can choose,
from 1 to the maximum of all piles.
step 1-> Define a monotonic function eg-> isEat()
If the function returns true for a value of k, it will also return true for all greater values of k.
This is because if Koko can eat all the bananas in h hours at speed k,
then she can also eat all the bananas in h hours at any greater speed.
For example, consider the piles of bananas [3, 6, 7, 11] and h = 8.
If Koko can eat the bananas at speed k = 11, then she must also be able to
eat the bananas at speeds 12, 13, 14, ... and so on. In order to minimize the speed,
we need to find the lowest possible speed at which Koko can eat all the bananas.
We can visualize the valid search space as follows:
0 1 2 3 4 5 6 7 8 9 10 (11 12 13 ... These speeds allow Koko to eat the bananas)
Now, our goal is to find the lowest speed. We start by considering the entire
search space from 0 to 10. As we perform a binary search, we gradually reduce
the search space. Eventually, we find a point where Koko is not able to eat the
bananas, which becomes the boundary.
(False part) 0 1 2 3 | 4 5 6 7 ... (True part)
In this case, k = 3 is the boundary speed. Koko is not able to eat the bananas at
speeds below this. Therefore, we need to find the minimum speed, which is 4.
In the code, we attempt to divide the search space by checking if Koko can eat
the bananas at a certain speed. If she can, we move towards lower speeds by updating
low = mid + 1. If she cannot eat the bananas, we move towards higher speeds by
updating high = mid - 1. This binary search approach helps us find the minimum
speed at which Koko can eat all the bananas.class Solution {
public:
bool iseat(int k , int h , vector<int>&piles)
{ long long cnt=0;
for (int i=0 ; i< piles.size();i++)
{
if(piles[i]%k)cnt++;
cnt+=piles[i]/k;
}
return h>=cnt;
}
int minEatingSpeed(vector<int>& piles, int h) {
int low= 1 , high=1e9,ans=INT_MAX;
sort(piles.begin(), piles.end());
while(high>=low)
{
int mid=(low+high)/2;
if(iseat(mid, h,piles))
{
high=mid-1;
ans =min (ans ,mid);
}
else
{
low=mid+1;
}
}
return ans ;
}
};So here is general approach of binary search
int BinarySearchTemplate(vector<int>& v, int cond)
{
int low= 0 , high=somehighvalue,ans=choose value according to question;
while(high>=low)
{
int mid=(low+high)/2;
if(findisBoundary(mid, h,cond))
{
Two case
//1. shrink high=mid-1 or mid+1 and calucate answer
//2. shring low=mid+1 or mid+1 and calculate answer
}
else
{
Two case
//1. shrink high=mid-1 or mid+1 and calucate answer
//2. shring low=mid+1 or mid+1 and calculate answer
}
}
return ans ;
}Let's redefine the findIsBoundary concept in binary search.
In binary search problems, our objective is to locate a boundary
within the search space. For example, consider the task of finding a
target element in a sorted array:
0 1 2 (Target: 3) 4 5
In this case, the target element serves as the boundary between the elements
smaller than the target and greater than the target By comparing the middle element with the target, we can determine
if the current element is on the boundary.
Similarly, in the Koko problem, we aim to find the first occurrence of a true condition.
This true condition represents the boundary between the false elements and the true
elements. By formulating the problem in terms of true and false conditions, we can search
for the first true occurrence or the specific boundary required by the problem.
So in any Probklem define your problem in true and false and return first true or false
according to question
This image is taken from geeksforgeek
For instance, when searching for the lower bound of an element:in lower bound we return first true
1 2 3 4 5 (7) 8 9 10 11
[f f f f f ( First True ) T T T T... so on if 7 lower bound
suppose if 7 us is not present then first true is
8 so 8 is lowerbound in that case Basically you have to find boundary condition in binary search
That why you have to minimum possible answer and maximum possible sum like this type of question in binary search .
eg->
Aggressive Cows: minimum distance between any two of them is the maximum possible.
May you get my point of view
Allocate Minimum Number of Pages from N books to M students
Find minimum cost to buy all books
Some more example of avove format
#define ll long long
class Solution {
public:
bool ispos(ll mid,ll Totaltrip,vector<int>&trip)
{
long long cnt=0;
for(auto t:trip)
cnt+=(mid/t*1ll);
return cnt>=Totaltrip;
}
long long minimumTime(vector<int>& time, int totalTrips)
{
ll l=0,h=1e14,mid=0,ans=0;
while(h>=l)
{
mid=(h+l)/2;
if(ispos(mid,totalTrips,time))
ans=mid,h=mid-1;
else l=mid+1;
}
return ans;
}
};class Solution {
public:
bool ispos(int speed ,double hour ,vector<int>&v)
{
double Ttime =0;
for (int i=0 ; i< v.size()-1 ;i++)
{
Ttime+=v[i]/speed;
if (v[i]%speed)Ttime++;
}
Ttime+=v[v.size()-1]*1.0/speed;
return hour>=Ttime;
}
int minSpeedOnTime(vector<int>& dist, double hour) {
int low=1 ,high=1e9+6,mid,ans=INT_MAX;
while (high>= low)
{
mid= (high+low) /2;
if (ispos(mid, hour , dist))
ans = min (ans , mid),high=mid-1;
else low = mid+1;
}
if(ans==INT_MAX) return -1;
return ans;
}
};// simple one
class Solution {
public:
int isboundary(int limit,int m ,int n)
{
int ans = 0;
for(int i = 1; i <= m; i++)
ans += min(limit / i, n);
return ans;
}
int findKthNumber(int m, int n, int k) {
int low=1, high=m*n , mid,ans=0;
while (high > low)
{
mid=(high+low)/2;
if(isboundary(mid , m , n) < k)
ans= low, low= mid+1;
else high=mid;
}
return ans;
}
};class Solution {
public:
bool isboundary(int limit ,int k, vector<int>&nums)
{
// This question is exact same as bookallocation problem
long long cnt=0 ,sum=0 ;
for(int i=0;i<nums.size();i++)
{
if(nums[i]>limit)return false;
if(sum+nums[i]>limit)
{
cnt++;
sum=nums[i];
}
else sum+=nums[i];
}
return (cnt < k);
// cnt< k as for N division we have to make n-1 cut (Focus this )
}
int splitArray(vector<int>& nums, int k) {
long long low=0, high=1e9, mid,ans=INT_MAX;
while(high>=low)
{
mid=(low+high)/2;
if(isboundary(mid,k, nums))
ans =min(ans ,mid),high=mid-1;
else low=mid+1;
}
return ans ;
}
};- Maximum-profit-in-job-scheduling
If we see closely, we can either take the interval or we cannot take that interval. From there we can easily think about DP approach. Now when you are taking an interval you need to figure out what is the next interval you can take.
For example, if we take an interval (1,3) the next valid interval to consider should have start time from 3. Now upon loking at the constraints we can observe that binary search is required to find the next index.
class Solution {
public:
int getnext(vector<vector<int>>&job,int lo , int target)
{
int n=job.size();
int hi=n-1,mid=0,ans=n+1;
while(hi>=lo)
{
mid= (lo+hi)/2;
if(job[mid][0]>=target)
ans=mid ,hi=mid-1;
else lo=mid+1;
}
return ans;
}
int solve (int idx ,vector<vector<int>>&job,vector<int>&dp)
{
int n=job.size();
if(idx>=n)return 0;
if(dp[idx]!=-1)return dp[idx];
auto next=getnext(job ,idx+1,job[idx][1]);
// solve for taken or not taken
int nottaken=solve(idx+1,job,dp);
int taken=job[idx][2]+solve(next,job,dp);
return dp[idx]=max(taken ,nottaken);
}
int jobScheduling(vector<int>& startTime, vector<int>& endTime, vector<int>& profit)
{
int n=startTime.size();
// create input
vector<int>dp(500000+5,-1);
vector<vector<int>>job(n , vector<int>(3,0));
for(int i=0 ; i< n ;i++)
{
job[i][0]=startTime[i];
job[i][1]=endTime[i];
job[i][2]=profit[i];
}
// sort input according to start time;
auto cmp=[&](auto vec1 ,auto vec2)
// just for practice
{
return vec1[0]<=vec2[0];
};
sort(begin(job),end(job), cmp); // by default sort according to first
return solve(0,job,dp);
}
};Actually this will introduce you meet in middle algo so go and learn from above link
code of above person
class Solution {
public:
vector<vector<int>> FindSubset(int l ,int r, vector<int>&nums)
{
int n=r-l+1;
vector<vector<int>> Allsubset(n+1);
for(int i=0 ;i < (1<<n );i++)
{
int sum=0,subsetSize=0;
for(int j=0 ;j<n;j++)
{
int bits=(1<<j);
if(!(bits&i))continue;
sum+=nums[l+j];
subsetSize++;
}
Allsubset[subsetSize].push_back(sum);
}
return Allsubset;
}
int minimumDifference(vector<int>& nums)
{
int totalSum = accumulate(begin(nums), end(nums), 0);
int n = nums.size();
auto left=FindSubset(0,n/2-1,nums);
auto right=FindSubset(n/2,n-1,nums);
int target=totalSum/2,ans=INT_MAX;
// cacluate answer
// if we have taken i the subset from left the we must have to take n-i
// length from right subset
int N=n/2;
for(int i=0 ;i<=N;i++)
{
auto r=right[N-i];
sort(begin(r),end(r));
for(auto currleftsum:left[i])
{
int NeedRightsum=target-currleftsum;
auto it = lower_bound(begin(r), end(r),NeedRightsum);
if (it != end(r))
ans = min(ans, abs(totalSum - 2 * (currleftsum + *it)));
}
}
return ans;
}
};some important questions
- Kth Smallest Element in a Sorted Matrix
- Median of Two Sorted Arrays
- Capacity to Ship Packages Within D Days
- The Latest Time to Catch a Bus
- Sum of Mutated Array Closest to Target
- Number of Subsequences That Satisfy the Given Sum Condition
- Search a 2D Matrix
- Longest Increasing Subsequence
- Search in Rotated Sorted Array
- Peak Index in a Mountain Array
You can solve more questions but in my point of if you solve all above discussed question you have feel of binary search
My Other post:
If you stuck in bits I must say follow this
a. All-types-of-patterns-for-bits-manipulations-and-how-to-use-it
b. Mastering-sliding-window-technique-a-comprehensive-guide
If you found it helpful, please upvote. If you have any questions or comments, please feel free to leave them below. I'd love to hear your thoughts.
