Binary Search: Maximum and Minimum Concepts

Binary Search: Maximum and Minimum Concepts

In this blog, we will explore how binary search can be used to solve problems that involve finding the maximum or minimum value satisfying a specific condition. We'll also look at how to identify such problems, provide examples, and share a reusable template for solving them.

1. How to Identify if a Problem is a Binary Search Problem (Maximum/Minimum)

Binary search is not just limited to searching in sorted arrays. It can also be applied to problems where you need to find the maximum or minimum value that satisfies a certain condition. Here are some key indicators to identify such problems:

• Monotonic Function: The problem involves a function that is either increasing or decreasing. For example:
  • In an increasing function, For every x > y f(x) >= f(y)
  • In a decreasing function, For every x > y f(x) <= f(y)
• Search Space: The problem has a well-defined search space (e.g., a range of values) where the answer lies.
• Optimization: The problem requires finding the minimum or maximum value that meets a certain condition.

2. Example Problems

Example 1: Finding the Minimum Value (Increasing Function)

Problem: You are given an array time where time[i] denotes the time taken by the ith bus to complete one trip. Each bus can make multiple trips successively, and all buses operate independently. You are also given an integer totalTrips, which denotes the number of trips all buses should make in total. Return the minimum time required for all buses to complete at least totalTrips trips.

Example 1:

Input: time = [1,2,3], totalTrips = 5
Output: 3
Explanation:
- At time t = 1, trips completed: [1, 0, 0]. Total trips = 1.
- At time t = 2, trips completed: [2, 1, 0]. Total trips = 3.
- At time t = 3, trips completed: [3, 1, 1]. Total trips = 5.
So, the minimum time needed is 3.

Example 2:

Input: time = [2], totalTrips = 1
Output: 2
Explanation:
There is only one bus, and it completes its first trip at t = 2.

Solution Code:

class Solution {
public:
    long long f(vector<int>& time, long long val) {
        long long a = 0;
        for (int i = 0; i < time.size(); i++) {
            a += val / time[i];
        }
        return a;
    }

    long long minimumTime(vector<int>& time, int totalTrips) {
        long long low = 1, high = 1e14;
        while (low < high) {
            long long mid = low + (high — low) / 2;
            if (f(time, mid) >= totalTrips)
                high = mid;
            else
                low = mid + 1;
        }
        return high;
    }
};

Explanation of the Code:

1. Function f:
   • This function calculates the total number of trips completed by all buses in val time.
   • For each bus, the number of trips it can complete in val time is val / time[i].
   • The function sums up the trips for all buses and returns the total.
   • Why is f increasing? As val increases, the number of trips each bus can complete also increases. Therefore, f(val) is an increasing function.
2. Binary Search Setup:
   • low = 1: The minimum possible time is 1.
   • high = 1e14: The maximum possible time is based on the constraints. Since time[i] <= 1e7 and totalTrips <= 1e7, the worst-case scenario is when there’s only one bus with time[i] = 1e7, and we need 1e7 trips. So, the maximum time required is 1e7 * 1e7 = 1e14.
3. Binary Search Logic:
   • We perform binary search on the time range [1, 1e14].
   • For each mid, we calculate the total trips using f(time, mid).
   • If f(time, mid) >= totalTrips, it means we can achieve the required trips in mid time or less. So, we update high = mid to search for a smaller time.
   • If f(time, mid) < totalTrips, we need more time, so we update low = mid + 1.
   • The loop continues until low and high converge, and we return high as the minimum time.

Example 2: Finding the Maximum Value (Decreasing Function)

Problem: Koko loves to eat bananas. There are n piles of bananas, where the ith pile has piles[i] bananas. The guards will return in h hours. Koko can decide her eating speed k (bananas per hour). Each hour, she chooses a pile and eats k bananas. If the pile has fewer than k bananas, she eats all of them and stops eating for that hour. Return the minimum integer k such that she can eat all the bananas within h hours.

Example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4
Explanation:
- At k = 4, Koko takes [1, 2, 2, 3] hours to eat each pile. Total time = 8 hours.

Example 2:

Input: piles = [30,11,23,4,20], h = 5
Output: 30
Explanation:
- At k = 30, Koko takes [1, 1, 1, 1, 1] hours to eat each pile. Total time = 5 hours.

Solution Code:

class Solution {
public:
    int f(vector<int>& p, int mid) {
        int total_time = 0;
        for (int i = 0; i < p.size(); i++) {
            if (p[i] % mid == 0)
                total_time += (p[i] / mid);
            else
                total_time += (p[i] / mid) + 1;
        }
        return total_time;
    }

    int minEatingSpeed(vector<int>& p, int h) {
        int maxi = *max_element(p.begin(), p.end());
        int low = 1, high = maxi;
        while (low < high) {
            int mid = low + (high — low) / 2;
            if (f(p, mid) <= h)
                high = mid;
            else
                low = mid + 1;
        }
        return high;
    }
};

Explanation of the Code:

1. Function f:
   • This function calculates the total time required to eat all bananas at a given eating speed mid.
   • For each pile, the time taken is piles[i] / mid if divisible, otherwise (piles[i] / mid) + 1.
   • The function sums up the time for all piles and returns the total.
   • Why is f decreasing? As mid (eating speed) increases, the time taken to eat all bananas decreases. Therefore, f(mid) is a decreasing function.
2. Binary Search Setup:
   • low = 1: The minimum possible eating speed is 1.
   • high = maxi: The maximum possible eating speed is the maximum number of bananas in any pile (since eating faster than this won’t help).
3. Binary Search Logic:
   • We perform binary search on the eating speed range [1, maxi].
   • For each mid, we calculate the total time using f(p, mid).
   • If f(p, mid) <= h, it means Koko can eat all bananas within h hours at speed mid or less. So, we update high = mid to search for a smaller speed.
   • If f(p, mid) > h, Koko needs to eat faster, so we update low = mid + 1.
   • The loop continues until low and high converge, and we return high as the minimum eating speed.

3. Basic Template for Binary Search Problems for Maximum/Minimum

Here is a reusable template for solving binary search problems involving maximum or minimum values:

int/long long/bool f(....para....){
     //calculate f function value for mid;
}
int Binary_Search_For_Max_Min(....para....) {
    int low=1;
    int high=1e9; //depend on given question
    int ans=-1;
    while (low < high) {
        int mid = low + (high - low) / 2;
        if (f(....mid....other Required para....)) {
            //update high/low/ans according to question
        } else {
            //update high/low/ans according to question
        }
    }
    return low/high/ans; // or high, depending on the problem
}

4. What’s Next?

In the next blog, we will dive deeper into more advanced binary search techniques, including:

• Binary search for Finding maximum/minimum value part2
• Binary search on 2D arrays or matrices.
• Binary search on Count Number of pair type problem
• Solving more complex problems that require creative applications of binary search.

Stay tuned for more insights and happy coding!

Binary Search: From Basics to Medium-Difficult Problems

Binary search is one of the most fundamental algorithms in computer science. While most coders are familiar with its basic concept, many struggle to apply it to medium-difficult problems. This blog aims to bridge that gap by explaining the core concepts, providing practical examples, and sharing tips to tackle binary search problems effectively.

Binary Search: The Basics

Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Basic Algorithm Steps:

1. Start with the entire sorted array.
2. Compare the target value with the middle element.
3. If the target value is equal to the middle element, return the index.
4. If the target value is less than the middle element, repeat the search in the left half.
5. If the target value is greater than the middle element, repeat the search in the right half.

Short Code Example:

int binarySearch(vector<int>& arr, int target) {
    int low = 0, high = arr.size() — 1;
    while (low <= high) {
        int mid = low + (high — low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid — 1;
    }
    return -1; // Target not found
}

Lower Bound, Upper Bound, and Binary Search Built-in Functions

In C++, the STL provides built-in functions for binary search:

• lower_bound: Returns the first element that is not less than the target.
• upper_bound: Returns the first element that is greater than the target.
• binary_search: Returns true if the target exists in the array, otherwise false.

Example Code for Built-in Functions:

#include <iostream>
#include <vector>
#include <algorithm> // for lower_bound, upper_bound, binary_search

using namespace std;

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11};
    int target = 7;

    // lower_bound: First element not less than target
    auto lb = lower_bound(arr.begin(), arr.end(), target);
    if (lb != arr.end()) {
        cout << "Lower bound of " << target << " is at index: " << (lb — arr.begin()) << endl;
    }

    // upper_bound: First element greater than target
    auto ub = upper_bound(arr.begin(), arr.end(), target);
    if (ub != arr.end()) {
        cout << "Upper bound of " << target << " is at index: " << (ub — arr.begin()) << endl;
    }

    // binary_search: Check if target exists
    if (binary_search(arr.begin(), arr.end(), target)) {
        cout << target << " exists in the array." << endl;
    } else {
        cout << target << " does not exist in the array." << endl;
    }

    return 0;
}

Output:

Lower bound of 7 is at index: 3
Upper bound of 7 is at index: 4
7 exists in the array.

Can Binary Search Be Applied to Unsorted Arrays?

No, binary search requires the array to be sorted. If the array is unsorted, you must sort it first, which takes O(n log n) time. However, there are specific problems where binary search can be applied creatively, even if the array isn't explicitly sorted.

Problem: Finding the Last Positive Number in a Array

Given an array of length n, where the first i elements are positive (including 0) and the remaining elements are negative, find the index i.

Input:

10
5 6 7 -2 -8 -1 -4 -3 -5 -6

Output:

2 

output is 2 because arr[2]=7 which is last positive number in given array.

In this question array is not sorted but still we can solve using binary search.

Solution Code:

bool f(vector<int>& arr, int mid) {
    return arr[mid] >= 0;
}

int solve(vector<int>& arr, int n) {
    int low = 0, high = n — 1;
    if (arr[0] < 0) return -1;
    if (arr[n — 1] >= 0) return n — 1;
    int ans = -1;
    while (low <= high) {
        int mid = low + (high — low) / 2;
        if (f(arr, mid)) {
            ans = mid;
            low = mid + 1;
        } else {
            high = mid — 1;
        }
    }
    return ans;
}

Explanation of the Code

The function f checks if the element at the middle index is non-negative. The solve function performs the binary search:

• Edge Case 1: If the first element is negative, return -1 immediately, as there are no non-negative numbers in the array.
• Edge Case 2: If the last element is non-negative, return n — 1, as all elements in the array are non-negative.
• Binary Search Initialization: Set low = 0 and high = n — 1 to define the search space. Initialize ans = -1 to store the last valid index.
• Mid Calculation: Compute mid = low + (high — low) / 2 to avoid overflow and find the middle index.
• Condition Check: Use the function f to check if arr[mid] >= 0. If true, update ans = mid and move low = mid + 1 to search for a better (higher) valid index.
• Else Condition: If f returns false, move high = mid — 1 to search in the left half, as the current mid is not valid.
• Termination: The loop runs until low exceeds high. At this point, ans holds the last valid index where arr[mid] >= 0.

This approach ensures the search space is halved in each iteration, making the algorithm efficient with a time complexity of O(log n).

What’s New in Binary Search?

Binary search can be adapted to various problems by modifying the condition function and the update logic. Practice problems where you need to find the first or last occurrence of an element, or apply binary search on a function's output.

Practice Template

while (low <= high) {
    int mid = low + (high — low) / 2;
    if (condition(arr, mid)) {
        // Update low or high based on the problem
    } else {
        // Update low or high based on the problem
    }
}
return low; // or high, depending on the problem

What’s Next?

This blog for basic idea about Binary Search In the next blog, we will dive deeper into binary search techniques, including:

• Binary search on answer space (e.g., finding the minimum or maximum value satisfying a condition).
• Binary search on 2D arrays or matrices.
• Solve Good Question which can help to increase skill in Binary Search Problems

Happy coding!

The Sieve of Eratosthenes is an efficient algorithm used to find all prime numbers up to a given limit, n. It can also be modified to find the Smallest Prime Factor (SPF) for each number up to n. In this blog, we will understand the concept of Smallest Prime Factor (SPF) and how it is computed using the Sieve of Eratosthenes.

Definition

Prime Number: A prime number is a number greater than 1 that is only divisible by 1 and itself. For example, 7 is a prime number because its only divisors are 1 and 7. Similarly, 13, 17, 23, and so on are prime numbers.

Smallest Prime Factor (SPF): The Smallest Prime Factor (SPF) of a number n is the smallest prime number that divides n. If n is a prime number, its smallest prime factor is the number itself.

Example: For n = 35, the prime factorization is 35 = 5 * 7. Hence, the smallest prime factor (SPF) of 35 is 5, which is the smallest prime factor in the factorization.

Sieve of Eratosthenes for Computing SPF:

The Sieve of Eratosthenes can be used to precompute the Smallest Prime Factor (SPF) for all numbers from 1 to n. Here's the basic idea behind the algorithm:

Initially, assume that each number is its own smallest prime factor. For each prime number p, iterate through all multiples of p and set their smallest prime factor to p. This method allows us to compute the SPF for all numbers up to 100,000 efficiently in O(n log log n) time complexity.

C++ code of sieve for spf

 
const int MAX_VAL = 1e5 + 5; int spf[MAX_VAL]; 
void sieve() { 
  for (int i = 1; i <= 100000; ++i) {  spf[i] = i;  }
for (int i = 2; i * i <= 100000; ++i) {
    if (spf[i] == i) { 
        for (int j = i * i; j <= 100000; j += i) {
            if (spf[j] == j) { 
                spf[j] = i;
            }
        }
    }
}
}
int main() {  sieve();  return 0; }  

Use of spf

1. Check number is prime

  
 int a;
 cin>>a;
 if(spf[a]==a)
 cout<<"Given number is prime";
  

2. Check number is semi-prime
semi-prime: Product of two prime numbers (may be both are equal) Example: 25=5*5, 4=2*2, 77=7*11

  
 int a;
 cin>>a;
 int x=spf[a];
 int y=a/x;
 if(spf[x]==x && spf[y]==y)
 cout<<"Given number is semi-prime";
  

3. Given number have exactly 3 divisors?
Number have exactly 3 divisors only in case number is square of prime number
Example: 49 (divisors: 1 7 49),169 (divisors: 1 13 169)

  
 int a;
 cin>>a;
 int x=spf[a];
 int y=a/x;
 if(x==y && spf[x]==x && spf[y]==y)
 cout<<"Given number have exactly 3 divisors";
  

But what if Given number big like 1e8 (10^8) OR (10^9)? Then is algorithm is not work?
Answer: In that case First check number is perfect square or not. If number is perfect square then check square root is prime number or not square root(10^8)=10000 and square root(10^10)=100000

  
 int a;
 cin>>a;
 int sq=sqrt(a); 
 if(sq*sq==a && spf[sq]==sq)
 cout<<"Given number have exactly 3 divisors";
  

4. Finding the Prime Factorization of a Number

  
 int n;
 cin>>n;
 int x=n;
 while(x!=1){
 cout<<spf[x]<<" ";
 x=x/spf[x];
 }
  

  
 Input: 60
 Output: 2 2 3 5
  

5. Check numbers are co-prime

  
 // Function to compute the prime factorization of a number n 
 // The result is returned as a sorted vector of prime factors. 
 vector < int > factorization(int n){
 vector < int > ans;
 int x=n;
 while(x!=1){
 ans.push_back(spf[x]); x=x/spf[x];
 }
 return ans;
 }
 
 
 // Function to check if two sorted vectors have no common elements 
 // It returns true if the vectors have no common elements, otherwise false 
 bool have_no_common_element(vector < int > &a,vector < int > &b){
 int p1=0,p2=0;
 while(p1<a.size() && p2<b.size()){
 if(a[p1]==b[p2])
 return false;
 else if(a[p1]<b[p2])
 p1++;
 else
 p2++; }
 return true;
 }
 
 
 int a,b;
 cin>>a>>b;
 vector < int >factor_of_a=factorization(a);
 vector < int >factor_of_b=factorization(b);
 if(have_no_common_element(factor_of_a,factor_of_b))
 cout<<"Given numbers are co-prime";
  

Also, Directly use in built __gcd() function this is better way

int a,b;

cin>>a>>b;

if(__gcd(a,b)==1)

cout<<"Given numbers are co-prime";