DSA - Binary Search

Recoggnize a Binary Search Problem

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)

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