First Match, and Searching for the Answer

Find the first one that's big enough

Often you don't want any match – you want the first position where a[i] >= x. Keep going after a match, remembering it, and look further left:

public class Main {
    static int firstAtLeast(int[] a, int x) {
        int lo = 0, hi = a.length - 1, answer = a.length;   // a.length = "none"
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (a[mid] >= x) {
                answer = mid;      // good, but maybe there's an earlier one
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return answer;
    }

    public static void main(String[] args) {
        int[] scores = {35, 50, 50, 50, 72, 88, 91};
        System.out.println(firstAtLeast(scores, 50));   // first 50
        System.out.println(firstAtLeast(scores, 60));   // first score >= 60
        System.out.println(firstAtLeast(scores, 99));   // none: 7
    }
}

Output

1
4
7

The number of scores >= x is length − firstAtLeast(x). Two of these searches can count how many values fall in any range – in O(log n).

Binary search on the answer

Some problems ask for the smallest value that works, and you can easily check whether a value works. If “works” is false, false, …, false, true, true, true – binary search the switch point!

Example: what is the smallest whole number whose square is at least 2,000,000?

public class Main {
    public static void main(String[] args) {
        long target = 2000000;
        long lo = 0, hi = target, answer = target;
        int checks = 0;
        while (lo <= hi) {
            long mid = lo + (hi - lo) / 2;
            checks++;
            if (mid * mid >= target) {   // works: try smaller
                answer = mid;
                hi = mid - 1;
            } else {                     // doesn't work: go bigger
                lo = mid + 1;
            }
        }
        System.out.println(answer + " found with " + checks + " checks");
    }
}

Output

1415 found with 21 checks

Remember: Binary search works on anything that's “sorted” in the true/false sense – not just arrays.