Binary Search: Arithmetic and Mathematical Edge Cases

Guess Number Higher or Lower (LeetCode 374)

A simple ternary logic search based on external feedback.

public int guessNumber(int n) {
    int low = 1, high = n;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        int res = guess(mid); // API returns: -1 (high), 1 (low), 0 (correct)
        if (res == 0) return mid;
        else if (res < 0) high = mid - 1;
        else low = mid + 1;
    }
    return low;
}

Valid Perfect Square (LeetCode 367)

Determine if a number is a perfect square without using built-in square root functions.

public boolean isPerfectSquare(int num) {
    if (num < 1) return false;
    long low = 1, high = num; // Use long for mid * mid overflow
    while (low <= high) {
        long mid = low + (high - low) / 2;
        long square = mid * mid;
        if (square == num) return true;
        else if (square < num) low = mid + 1;
        else high = mid - 1;
    }
    return false;
}

Sqrt(x) (LeetCode 69)

Find the integer square root. Since we need the largest k such that k * k <= x, we look for the right-hand boundary.

public int mySqrt(int x) {
    if (x == 0) return 0;
    int low = 1, high = x;
    while (low < high) {
        // Ceiling mid calculation to avoid infinite loop when high = low + 1
        long mid = low + (high - low + 1) / 2;
        if (mid * mid <= (long) x) {
            low = (int) mid; // Mid is a valid floor root, keep it
        } else {
            high = (int) mid - 1;
        }
    }
    return low;
}

Pow(x, n) (LeetCode 50: Exponentiation by Squaring)

This is a Binary Divide & Conquer approach (Fast Exponentiation).

public double myPow(double x, int n) {
    long power = n; // Use long to handle Integer.MIN_VALUE edge cases
    if (power < 0) {
        x = 1 / x;
        power = -power;
    }
    return fastPow(x, power);
}

private double fastPow(double x, long n) {
    if (n == 0) return 1.0;
    double half = fastPow(x, n / 2);
    // x^n = (x^(n/2))^2 if even, else (x^(n/2))^2 * x
    return (n % 2 == 0) ? half * half : half * half * x;
}

Summary Selection Guide