DSA - Binary Search

Recoggnize a Binary Search Problem

1. Sorted List / monotonic

2. minimize Maxima

3. maximize Minima

4. Optimization - if you have solved a problem and they ask you to optimize it then Binary Search is one of the widely used approach.

5. 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),

1. will return the number greater or equal to n

2. 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)

1. will return the number STRICTLY greater to n

2. 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

1. BS On Answer

   • Atomic Items contribution

   • Sweep Coverage

   • 2D Variations

2. 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

Mapping a 1D Index to a 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.

Calculation of x and y

1. 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).

2. 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.

Example

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

Code Context

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.