Binary Search DSA Problems

Binary Search DSA Problems | Also see:- Linear search, Binary search, and Problems on Binary Search. Let us see some more problems on the Binary Search.

Table of Contents

• 1. Find the Minimum in the Rotated Sorted Array
• 2. Single Element in a Sorted Array
• 3. Find nth root of m
• 4. Koko Eating Bananas
• 5. Minimum Number of Days to Make m Bouquets
• 6. Find the Smallest Divisor Given a Threshold

---

1. Find the Minimum in the Rotated Sorted Array

Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], …, a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], …, a[n-2]].

Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time. Problem Link:- 153. Solution

public class Test {
    public static void main(String[] args) {
        int arr[] = { 3, 4, 5, 1, 2 };
        System.out.println(findMin(arr)); // 4
    }

    public static int findMin(int[] nums) {
        int n = nums.length, left = 0, right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // Check if the middle element is greater than the right element
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return nums[left];
    }
}

The same question can be asked to find out how many times has an array been rotated, the solution is the same. Actually, you have to find out the index of the minimum element.

2. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once. Return the single element that appears only once. Problem: 540

Your solution must run in O(log n) time and O(1) space.

Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2

Input: nums = [3,3,7,7,10,11,11]
Output: 10

In the binary search for finding the single non-duplicate element in a sorted array, you choose to go left or right based on the relationship between the middle element and its neighbors. Here are the key points to decide:

1. Check the Middle Element:

• If the middle element is not equal to its neighbors (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]), then it’s the unique element, so return nums[mid].

2. Determine the Half to Search:

• Odd and Even Index Patterns:
  • If mid is even:
  • If nums[mid] == nums[mid + 1], the single element is in the right half.
  • Otherwise, it’s in the left half.
  • If mid is odd:
  • If nums[mid] == nums[mid - 1], the single element is in the right half.
  • Otherwise, it’s in the left half.

3. Update Pointers:

• Adjust the low and high pointers based on the observations above:
  • Move low to mid + 1 if the single element is in the right half.
  • Move high to mid - 1 if the single element is in the left half.

Example Decision Process:
For example, if mid is 6 and nums[mid] == nums[mid + 1]:

• Since mid is even, and nums[mid] == nums[mid + 1], the single element must be in the right half. So, set low = mid + 1.

On the other hand, if mid is 7 and nums[mid] == nums[mid - 1]:

• Since mid is odd, and nums[mid] == nums[mid - 1], the single element must be in the right half. So, set low = mid + 1.

class Solution {
    public int singleNonDuplicate(int[] nums) {
        int n = nums.length;

        // Edge case: Single element in the array
        if (n == 1) {
            return nums[0];
        }

        // Edge case: Unique element at the beginning
        if (nums[0] != nums[1]) {
            return nums[0];
        }

        // Edge case: Unique element at the end
        if (nums[n - 1] != nums[n - 2]) {
            return nums[n - 1];
        }

        int low = 1, high = n - 2;

        // Binary search to find the unique element
        while (low <= high) {
            int mid = low + (high - low) / 2;

            // Check if mid is the unique element
            if ((nums[mid] != nums[mid - 1]) && (nums[mid] != nums[mid + 1])) {
                return nums[mid];
            }

            // Adjust low and high pointers
            if ((mid % 2 == 1 && nums[mid] == nums[mid - 1]) || (mid % 2 == 0 && nums[mid] == nums[mid + 1])) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return -1; // This line should never be reached due to problem constraints
    }
}

3. Find nth root of m

You are given 2 numbers n and m, the task is to find n√m (nth root of m). If the root is not integer then returns -1. Problem. Solution

Naive Solution

public class Test {
    public static void main(String[] args) {
        int n = 2, m = 9;
        System.out.println(nthRoot(n, m)); // Output: 3
    }

    private static int nthRoot(int n, int m) {
        // Iterate from 1 to m to find the nth root of m
        for (int i = 1; i <= m; i++) {
            int pow = (int) Math.pow(i, n); // Calculate i^n
            if (pow == m) {
                return i; // Return i if i^n equals m
            } else if (pow > m) {
                return -1; // Return -1 if i^n exceeds m
            }
        }
        return -1; // Return -1 if no such i is found
    }
}

Time complexity: O(m * log n)

Let us analyze this program, we started with 1 and computed pow(1, n) and if it is greater than m then we go to the higher number, and if pow(i, n) > m then it means numbers greater than i will never be the result. Based on that we can eliminate our search space.

In Binary search find the mid index:-

• If pow(mid, n) == m then mid is the answer.
• Else if pow(mid, n) > m then go to numbers < mid [left half].
• Else go to the right half.

private static int nthRoot(int n, int m) {
    int low = 1, high = m;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int pow = (int) Math.pow(mid, n);

        if (pow == m) {
            return mid;
        } else if (pow > m) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

4. Koko Eating Bananas

Koko loves to eat bananas. There are n piles of bananas, the ith pile has piles[i] bananas. The guards have gone and will come back in h hours. Problem: 875. Solution

Koko can decide her bananas-per-hour eating speed of k. Each hour, she chooses some pile of bananas and eats k bananas from that pile. If the pile has less than k bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer k such that she can eat all the bananas within h hours.

public class Test {
    public static void main(String[] args) {
        int[] piles = { 3, 6, 7, 11 };
        int h = 8;
        System.out.println(minEatingSpeed(piles, h));
    }

    private static int minEatingSpeed(int[] piles, int h) {
        int k = 1;
        int actualHour = 0;
        while (actualHour != h) {
            int hours = 0;
            for (int i : piles) {
                hours += Math.ceil((double)i / k);
                if (hours > h) {
                    break;
                }
            }
            actualHour = hours;
            k++;
        }
        return k;
    }
}

Let us try to eliminate the searching range through binary search. Koko can eat maximum max(piles[]) bananas in our hour, and can eat minimum 1 banana per hour. If total hours < h then we have to search in right side (higher numbers than mid), else we have to search in left side (smaller numbers).

private static int minEatingSpeed(int[] piles, int h) {
    int low = 1, high = Arrays.stream(piles).max().getAsInt();

    while (low <= high) {
        int mid = low + (high - low) / 2;
        int hours = 0;

        for (int i : piles) {
            hours += Math.ceil((double) i / mid);

            if (hours > h) {
                break;
            }
        }

        if (hours <= h) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return low;
}

5. Minimum Number of Days to Make m Bouquets

You are given an integer array bloomDay, an integer m and an integer k. Problem: 1482. Solution

When it is impossible to make m Bouquets? Consider the max(array), on that day all flowers are bloomed, and if we can’t make bouquets when all the flowers are bloomed then it is impossible to make on previous days. Therefore max day = max(array).

We can create the Bouquet when at least 1 flower is bloomed therefore the minimum possible day = min(array). It reduces our search space to [min(array), max(array)].

public class Test {
    public static void main(String[] args) {
        int[] bloomDay = { 1, 10, 3, 10, 2 };
        int m = 3, k = 2;
        System.out.println(minDays(bloomDay, m, k));
    }

    public static int minDays(int[] bloomDay, int m, int k) {
        int low = bloomDay[0], high = bloomDay[0];
        for (int a : bloomDay) {
            low = Math.min(low, a);
            high = Math.max(high, a);
        }
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (totalBoquets(bloomDay, mid, k, m)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private static boolean totalBoquets(int[] bloomDay, int j, int k, int m) {
        int bouquets = 0, count = 0;
        for (int i : bloomDay) {
            if (i <= j) {
                count++;
                if (count == k) {
                    bouquets++;
                    count = 0;
                }
            } else {
                count = 0;
            }
            if (bouquets >= m) {
                return true;
            }
        }
        return false;
    }
}

6. Find the Smallest Divisor Given a Threshold

Given an array of integer nums and an integer threshold, we will choose a positive integer divisor, divide all the array by it, and sum the division’s result. Find the smallest divisor such that the result mentioned above is less than or equal to the threshold. Problem: 1283. Solution

Each result of the division is rounded to the nearest integer greater than or equal to that element. (For example: 7/3 = 3 and 10/2 = 5).

class Solution {
    public int smallestDivisor(int[] nums, int threshold) {
        int low = 1, high = Arrays.stream(nums).max().getAsInt();

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isThreshold(nums, mid, threshold)) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private boolean isThreshold(int[] nums, int divisor, int threshold) {
        int sum = 0;
        for (int i : nums) {
            sum += Math.ceil((double) i / divisor);
            if (sum > threshold) {
                return false;
            }
        }
        return true;
    }
}

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!

Search