Successful Binary Searches Irrespective of Pivot

Problem Overview

Ordinary binary search depends on which mid is chosen when several indices are valid.

Intuition

Ordinary binary search depends on which mid is chosen when several indices are valid. Here the question is which values are found no matter how that choice is made. If every value to the left of arr[i] is smaller and every value to the right is larger, then a mid on the left always moves right and a mid on the right always moves left, so the search is forced onto i. That is exactly the positions that are a left-to-right maximum and sit strictly below the minimum of the suffix to their right.

Algorithm

1Build an array suf where suf[i] is the minimum of arr[i] through arr[n - 1], scanning from the right.
2Walk from left to right while tracking the maximum seen so far.
3For each index before the last, if arr[i] is greater than that maximum and strictly less than suf[i + 1], count it.
4Update the running maximum whenever arr[i] is larger.
5After the loop, count the last index if it is greater than the running maximum, because it has no right side to check.

Example Walkthrough

Input: arr = [1, 3, 2]

1. The suffix minima are 1, 2, 2.
2. Index 0 holds 1, which is a new maximum and is less than the suffix minimum 2 on its right, so it counts.
3. Index 1 holds 3, which beats the left maximum 1, but 3 is not less than the right minimum 2, so it does not count.
4. Index 2 holds 2, which is not greater than the left maximum 3.

Output: 1

Common Pitfalls

• The right side test is strict. Equal values on the right can send the search the wrong way.
• Only left-to-right maxima can qualify, so positions that lose to an earlier larger value are skipped.
• The last index has an empty right side, so it only needs to beat the left maximum.
• Building the suffix minima takes linear extra memory. Recomputing the right minimum for every index would be quadratic.

Successful Binary Searches Irrespective of Pivot.java

Java

// Approach: Binary search finds arr[i] no matter how the mid is chosen exactly
// when every left value is smaller and every right value is larger. Then a mid
// on the left always goes right, and a mid on the right always goes left. That
// means arr[i] is a left-to-right maximum and is strictly below the suffix
// minimum on its right. One backward pass builds those suffix minima; one
// forward pass counts the positions that pass both tests.
// Complexity: O(n) time, O(n) extra space.
class Solution {
    public int countAlwaysFound(int[] arr) {
        int n = arr.length;
        if (n == 0)
            return 0;

        int[] suf = new int[n];
        suf[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--)
            suf[i] = arr[i] < suf[i + 1] ? arr[i] : suf[i + 1];

        int mx = Integer.MIN_VALUE;
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > mx) {
                if (arr[i] < suf[i + 1])
                    cnt++;
                mx = arr[i];
            }
        }
        if (arr[n - 1] > mx)
            cnt++;
        return cnt;
    }
}

Was this solution helpful?