Looks like no one added any tags here yet for you.
Recoggnize a Binary Search Problem
Sorted List / monotonic
minimize Maxima
maximize Minima
Optimization - if you have solved a problem and they ask you to optimize it then Binary Search is one of the widely used approach.
N = 10^5 and values are 10^9 / 10^8
Binary Search AZ Way
convert the array so that it’s a series of 0s and 1s and then just return the first occurrence of 1.
A = [0, 0 ,0, 0, 0 , 1, 1, 1, 1]
We need to find the first occurrence of 1.
if l and r are given, how do you calculate mid?
l + (r-l)/2 because (l+r)/2 can overflow
Lowerbound (arr, n),
will return the number greater or equal to n
or will return num of elements < x, by subtracting what we got from 1 by start of array
example arr = [1, 3, 5, 5, 7, 7, 9]
lb(arr, 5) = 5 or iterator pointing to index 2
now if we subtract 2- 0 = num of elements smaller than 5
upperbound(arr, n)
will return the number STRICTLY greater to n
or will return num of elements <= x, by subtracting what we got from 1 by start of array
example arr = [1, 3, 5, 5, 7, 7, 9]
ub(arr, 5) = 7 or iterator pointing to index 4
now if we subtract 4- 0 = num of elements smaller or equal to 5
ub(arr, 9) = arr.end
template for binary search problems
int check(vector<int> &a, int m)
{
if (a[m] < a[0])
return 1;
return 0;
}
void solve(vector<int> &a)
{
int l = 0, r = a.size() - 1, ans = 0;
while (l <= r)
{
int m = l + (r - l) / 2;
if (check(a, m) == 0)
{
l = m + 1;
}
else
{
ans = m;
r = m - 1;
}
}
cout << ans << '\n';
}
Important answer is what we need to return when we won’t find the number in the array
Check is the main function which converts our array into 0 0 0 1 1 1 kind of array
for lower bound (number greater than or equal to x)
int check(vector<int> &a, int m, int x)
{
if (a[mid] <= x) mid] < x) //compare mid with the given element
return 1;
return 0;
}
eg this logic will convert
[1, 3, 5, 5, 7, 7, 9] and x = 5
into 0 0 1 1 1 1 1, so any element greater or equal to 5 will be converted to 1, rest all to 0, so answer will be 5 or index(2)
C++: binary_search
In C++, the Standard Template Library (STL) provides binary_search
in the <algorithm>
header.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 3, 5, 7, 9};
if (binary_search(arr.begin(), arr.end(), 5)) {
cout << "5 is present\n";
} else {
cout << "5 is not present\n";
}
return 0;
}
Returns true
if the element is found, otherwise false
.
The range [begin, end)
must be sorted.
C++'s STL also provides lower_bound()
and upper_bound()
in the <algorithm>
header.
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
vector<int> arr = {1, 3, 5, 7, 9};
auto lb = lower_bound(arr.begin(), arr.end(), 5);
auto ub = upper_bound(arr.begin(), arr.end(), 5);
cout << "Lower bound of 5: " << (lb - arr.begin()) << "\n"; // Output: 2
cout << "Upper bound of 5: " << (ub - arr.begin()) << "\n"; // Output: 3
return 0;
}
lower_bound()
returns an iterator to the first element greater than or equal to the given value.
upper_bound()
returns an iterator to the first element greater than the given value.
Both require the range [begin, end)
to be sorted.
Python: bisect.bisect_left()
and bisect.bisect_right()
Python provides the bisect
module for binary search operations.
import bisect
arr = [1, 3, 5, 7, 9]
index = bisect.bisect_left(arr, 5)
if index < len(arr) and arr[index] == 5:
print("5 is present at index", index)
else:
print("5 is not present")
bisect_left()
returns the position where the value should be inserted to maintain sorted order. « lowerbound
bisect_right()
gives the position after the last occurrence of the value. « upperbound
The array must be sorted.
for upper bound (number Strictly greater than x)
int check(vector<int> &a, int m, int x)
{
if (a[mid] < x) //compare mid with the given element
return 1;
return 0;
}
eg this logic will convert
[1, 3, 5, 5, 7, 7, 9] and x = 5
into 0 0 0 0 1 1 1, so any element greater or equal to 5 will be converted to 1, rest all to 0, so answer will be 7 or index(4)
Rotated Sorted Array
Check Function
int check(vector<int> &a, int mid, int x)
{
if (a[mid] < a[0]) //compare mid with first element
return 1;
return 0;
}
eg this logic will convert
3 4 5 1 2
into 0 0 0 1 1
we see that at the point of rotation, that is 1, is less than the first element 3, and so are all elements after 1, eg 2 in this case
For Bitonic array
Check Function
int check(vector<int> &a, int m, int x)
{
if (a[mid] > a[mid + 1]) //compare mid with the next element
return 1;
return 0;
}
eg this logic will convert
1 2 5 3 2 1
into 0 0 0 1 1 1
we see that at the point of rotation, that is 1, is less than the first element 3, and so are all elements after 1, eg 2 in this case
find one element which is single in an array of duplicate numbers
here we see that before the number the pairs are in even, odd position and after the number they change to odd, even position, so our check function will be
int check(vector<int> &A, int mid) {
if (mid %2 == 0) {
if (A[mid] == A[mid + 1])
return 0;
else return 1;
} else {
if (A[mid] == A[mid -1]) return 0;
return 1;
}
return 0;
}
so we need to convert
1 1 7 2 2 3 3 → 0 0 1 1 1 1 1
you see before the single digit 7, the pairs are in even odd position that is 0 and 1 and after 7 they shift a position by 1 so 2 2 are in 3 4 positions (odd, even) that;s what we do in the check function.
If mid is at even position then it’s next should be it’s duplicate, if the mid is at odd position then it’s prev should be it’s pair
Binary search types of problems
BS On Answer
Atomic Items contribution
Sweep Coverage
2D Variations
BS on Every Start - Can be done by 2 pointers
Binary search Time Complexity
Time complexity of check function * TC of check space
Painters partition problem
The Painter’s Partition Problem (or similar problems) fundamentally boils down to a pattern of partitioning an array into K subarrays in a way that minimizes the maximum sum of any subarray.
Time complexity of check function TC of check space = O(log(sum of array) *n
the search space will be from 0 to sum of all elements.We will see if for a given time
Binary search on answers problems so far, book allocation, painters problem, aggressive cows, this last one, place k points in given n points and the last one Given an array of integers A and an integer B, find and return the maximum value K such that there is no subarray in A of size K with the sum of elements greater than B, square root Can you summarize in a table what kind of problem is is maximizing the min or min the max, start, end values, what is the check function doing and what would be the transformation array 0 0 0 1 1 1 or 1 1 1 1 0 0 0
Problem | Goal | Search Range Start (Low) | Search Range End (High) | Check Function | Transformed Array Pattern |
Book Allocation | Minimize the maximum pages allocated to a student | 1 | Sum of all pages | Determines if current max pages per student is feasible (can allocate to all students within limit) | [0 0 0 1 1 1] |
Painter’s Partition | Minimize the maximum time needed for painters | 1 | Sum of all painting times | Determines if painters can paint all sections within a given time constraint | [0 0 0 1 1 1] |
Aggressive Cows | Maximize the minimum distance between cows | 1 | Maximum distance between the two furthest stalls | Checks if cows can be placed with at least the given distance between each other | [1 1 1 0 0 0] |
Place K Points Between N Points | Minimize the maximum separation between consecutive points | 1 | Maximum initial gap between consecutive points in sorted list | Determines if we can achieve a maximum separation by adding up to K points | [0 0 0 1 1 1] |
Array Subarray Sum Constraint | Maximize the minimum subarray size with sum <= B | 1 | Length of array N N N | Checks if a given subarray size has all subarrays with sum <= B | [1 1 1 0 0 0] |
Binary search - Aggressive cows - Check function
Approach:
The check
function is a key part of solving this problem. Its purpose is to determine if it’s possible to place C cows in the stalls such that the minimum distance between any two cows is at least a given distance d.
Place the First Cow: Start by placing the first cow in the first stall (position arr[0]
). This ensures we leave the largest possible space for the remaining cows.
Track Remaining Cows:
We initialize a count for the remaining cows (cows = c - 1
) since we’ve already placed the first cow.
We also keep track of the position of the last placed cow (prev = arr[0]
).
Place the Rest of the Cows:
Iterate through the stalls, starting from the second one.
For each stall, check if it’s at least d
distance away from the last placed cow.
If it is, place a cow there and update prev
to the current stall’s position.
Decrease the cows
count after placing a cow.
Check if All Cows Are Placed:
If all cows are placed successfully (i.e., cows == 0
), return true
, meaning it’s possible to place the cows with at least d
distance between them.
If Not All Cows Are Placed:
If the loop finishes and we haven’t placed all cows, return false
, meaning it’s not possible to place the cows with that distance.
Complexity:
Time Complexity: O(N)
We are iterating through the array once.
Space Complexity: O(1)
We have not used extra space.
bool check(int arr[], int d, int n, int c)
{
//Complete this function to check if c cows can be arranged into n stalls with d distance
int cows = c;
cows--;
int prev = arr[0];
for(int i=1; i<n; i++) {
if(arr[i] - prev >= d) {
cows--;
prev=arr[i];
}
if (cows==0) return true;
}
return false;
}
Binary search on 2D Matrix - mapping 1D index to 2D matrix
Given a 2D matrix A
with n
rows and m
columns, we can treat the matrix as a flattened 1D array of size n * m
. The index mid
in this 1D array needs to be converted back to the corresponding row and column indices in the 2D matrix.
x
and y
Row Index (x
):
The row index x
is calculated as mid / m
.
This works because dividing the 1D index by the number of columns (m
) gives the number of complete rows that fit into the index.
For example, if mid
is 7 and m
is 3, then x = 7 / 3 = 2
. This means the 7th element is in the 2nd row (0-based index).
Column Index (y
):
The column index y
is calculated as mid % m
.
This works because taking the modulus of the 1D index by the number of columns (m
) gives the position within the row.
For example, if mid
is 7 and m
is 3, then y = 7 % 3 = 1
. This means the 7th element is in the 1st column (0-based index) of the 2nd row.
Consider a 2D matrix:
A = [
[1, 3, 5],
[7, 9, 11],
[13, 15, 17]
]
This matrix has n = 3
rows and m = 3
columns.
If mid = 4
, then:
x = mid / m = 4 / 3 = 1
(integer division)
y = mid % m = 4 % 3 = 1
So, A[x][y]
corresponds to A[1][1]
, which is 9
.
Binary search on 2D Matrix - Code
In the provided code:
int Solution::searchMatrix(vector<vector<int>> &A, int B) {
int n = A.size();
if (n == 0) return 0;
int m = A[0].size();
int l = 0, r = m * n - 1;
while (l <= r) {
int mid = l + (r - l) / 2;
int x = mid / m;
int y = mid % m;
if (A[x][y] == B) return 1;
if (A[x][y] < B) l = mid + 1;
else r = mid - 1;
}
return 0;
}
mid
is the current index in the 1D representation of the matrix.
x = mid / m
calculates the row index.
y = mid % m
calculates the column index.
A[x][y]
accesses the element in the 2D matrix at the calculated row and column.
This approach allows the binary search to be performed on the 2D matrix as if it were a 1D array, ensuring efficient search operations.