Binary Search Interview Problems: Patterns, Pitfalls & Winning Strategies

public class ClassicBinarySearch {

    /**
     * Finds the exact index of a target in a sorted array.
     * Returns -1 if the target is not present.
     *
     * Time:  O(log n) — we halve the search space on every iteration
     * Space: O(1)    — no extra memory beyond a few pointers
     */
    public static int findExactIndex(int[] sortedPrices, int targetPrice) {
        int left = 0;
        int right = sortedPrices.length - 1;

        // Loop invariant: if targetPrice exists, it lives in sortedPrices[left..right]
        while (left <= right) {

            // Safe mid-point: avoids integer overflow for large indices
            int mid = left + (right - left) / 2;

            if (sortedPrices[mid] == targetPrice) {
                return mid;                       // Found it — return immediately
            } else if (sortedPrices[mid] < targetPrice) {
                left = mid + 1;                   // Target is in the RIGHT half
            } else {
                right = mid - 1;                  // Target is in the LEFT half
            }
        }

        return -1; // left has crossed right — target is not in the array
    }

    public static void main(String[] args) {
        int[] sortedPrices = {12, 25, 37, 49, 56, 68, 74, 89, 95};

        System.out.println(findExactIndex(sortedPrices, 56));  // Found at index 4
        System.out.println(findExactIndex(sortedPrices, 89));  // Found at index 7
        System.out.println(findExactIndex(sortedPrices, 100)); // Not present → -1
        System.out.println(findExactIndex(sortedPrices, 12));  // Edge: first element → 0
        System.out.println(findExactIndex(sortedPrices, 95));  // Edge: last element → 8
    }
}

public class BoundaryBinarySearch {

    /**
     * Finds the index of the FIRST occurrence of targetScore in a sorted array.
     * Returns -1 if not present.
     *
     * Key insight: when we find the target, we record it but keep searching LEFT
     * to see if an earlier occurrence exists.
     */
    public static int findFirstOccurrence(int[] sortedScores, int targetScore) {
        int left = 0;
        int right = sortedScores.length - 1;
        int firstIndex = -1; // Holds the best (leftmost) answer found so far

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (sortedScores[mid] == targetScore) {
                firstIndex = mid;      // Record this as our current best answer
                right = mid - 1;      // But keep looking LEFT for an earlier one
            } else if (sortedScores[mid] < targetScore) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return firstIndex;
    }

    /**
     * Finds the index of the LAST occurrence of targetScore in a sorted array.
     * Returns -1 if not present.
     *
     * Key insight: when we find the target, we record it but keep searching RIGHT
     * to see if a later occurrence exists.
     */
    public static int findLastOccurrence(int[] sortedScores, int targetScore) {
        int left = 0;
        int right = sortedScores.length - 1;
        int lastIndex = -1; // Holds the best (rightmost) answer found so far

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (sortedScores[mid] == targetScore) {
                lastIndex = mid;       // Record this as our current best answer
                left = mid + 1;        // But keep looking RIGHT for a later one
            } else if (sortedScores[mid] < targetScore) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return lastIndex;
    }

    public static void main(String[] args) {
        // Sorted array with duplicates — classic interview setup
        int[] sortedScores = {5, 10, 10, 10, 20, 30, 30, 45};

        System.out.println("First 10: " + findFirstOccurrence(sortedScores, 10));
        System.out.println("Last  10: " + findLastOccurrence(sortedScores, 10));

        System.out.println("First 30: " + findFirstOccurrence(sortedScores, 30));
        System.out.println("Last  30: " + findLastOccurrence(sortedScores, 30));

        // Count of 10s = lastIndex - firstIndex + 1
        int first = findFirstOccurrence(sortedScores, 10);
        int last  = findLastOccurrence(sortedScores, 10);
        System.out.println("Count of 10: " + (last - first + 1));

        // Target not present
        System.out.println("First 99: " + findFirstOccurrence(sortedScores, 99));
    }
}

public class RotatedArraySearch {

    /**
     * Searches for a target in a sorted-but-rotated array.
     *
     * Example rotation: [10, 20, 30, 40, 50] rotated at index 3
     *               =>  [40, 50, 10, 20, 30]
     *
     * Strategy: at every mid, figure out which half IS sorted,
     * then decide which half the target belongs to.
     *
     * Time:  O(log n)
     * Space: O(1)
     */
    public static int searchRotatedArray(int[] rotatedTemps, int targetTemp) {
        int left = 0;
        int right = rotatedTemps.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (rotatedTemps[mid] == targetTemp) {
                return mid; // Lucky — found it at the mid-point
            }

            // Determine which half is the "clean" sorted half
            if (rotatedTemps[left] <= rotatedTemps[mid]) {
                // LEFT half is cleanly sorted (no rotation in it)

                if (targetTemp >= rotatedTemps[left] && targetTemp < rotatedTemps[mid]) {
                    // Target is inside the clean left half — search there
                    right = mid - 1;
                } else {
                    // Target must be in the messy right half
                    left = mid + 1;
                }

            } else {
                // RIGHT half is cleanly sorted (no rotation in it)

                if (targetTemp > rotatedTemps[mid] && targetTemp <= rotatedTemps[right]) {
                    // Target is inside the clean right half — search there
                    left = mid + 1;
                } else {
                    // Target must be in the messy left half
                    right = mid - 1;
                }
            }
        }

        return -1; // Target not found in the array
    }

    public static void main(String[] args) {
        // Original sorted: [7, 18, 29, 40, 55, 63]
        // Rotated at pivot index 3: [40, 55, 63, 7, 18, 29]
        int[] rotatedTemps = {40, 55, 63, 7, 18, 29};

        System.out.println(searchRotatedArray(rotatedTemps, 18));  // In right segment → 4
        System.out.println(searchRotatedArray(rotatedTemps, 55));  // In left segment  → 1
        System.out.println(searchRotatedArray(rotatedTemps, 40));  // First element    → 0
        System.out.println(searchRotatedArray(rotatedTemps, 29));  // Last element     → 5
        System.out.println(searchRotatedArray(rotatedTemps, 100)); // Not present      → -1

        // Edge: single element
        int[] single = {42};
        System.out.println(searchRotatedArray(single, 42));  // → 0
        System.out.println(searchRotatedArray(single, 99));  // → -1
    }
}

public class AnswerSpaceBinarySearch {

    /**
     * PROBLEM: You're shipping packages with given weights over D days.
     * The ship has a weight capacity limit per day — packages load in order.
     * Find the MINIMUM possible capacity that lets you ship all packages in D days.
     *
     * WHY binary search? If capacity C works, then C+1 also works (more capacity = easier).
     * That monotonic relationship means we can binary search the answer space.
     *
     * Answer space:
     *   Minimum possible = max(packageWeights)  — must fit heaviest single package
     *   Maximum possible = sum(packageWeights)  — ship everything in one day
     */
    public static int minimumShipCapacity(int[] packageWeights, int daysAllowed) {

        // Left = smallest valid capacity (can't be less than the heaviest package)
        int left = 0;
        int right = 0;
        for (int weight : packageWeights) {
            left  = Math.max(left, weight);  // Must fit the heaviest single package
            right += weight;                 // Could always ship everything in 1 day
        }

        int minimumCapacity = right; // Worst-case starting answer

        while (left <= right) {
            int candidateCapacity = left + (right - left) / 2;

            if (canShipWithinDays(packageWeights, daysAllowed, candidateCapacity)) {
                // This capacity works — record it, then try to go LOWER (more efficient)
                minimumCapacity = candidateCapacity;
                right = candidateCapacity - 1;
            } else {
                // This capacity is too small — we need more
                left = candidateCapacity + 1;
            }
        }

        return minimumCapacity;
    }

    /**
     * Feasibility check: can we ship all packages within the day limit
     * using exactly this capacity per day?
     *
     * We greedily load each day's ship until adding the next package
     * would exceed the capacity, then start a new day.
     */
    private static boolean canShipWithinDays(
            int[] packageWeights, int daysAllowed, int capacity) {

        int daysNeeded    = 1;   // We always need at least 1 day
        int currentLoad   = 0;   // Weight loaded onto today's ship so far

        for (int weight : packageWeights) {
            if (currentLoad + weight > capacity) {
                // Adding this package would exceed today's limit — start a new day
                daysNeeded++;
                currentLoad = 0;

                if (daysNeeded > daysAllowed) {
                    return false; // Already exceeded our day budget — not feasible
                }
            }
            currentLoad += weight;
        }

        return true; // Shipped everything within the allowed days
    }

    public static void main(String[] args) {
        // Packages must ship in ORDER (can't reorder them)
        int[] packageWeights = {3, 2, 8, 4, 7, 5, 1, 6};
        int daysAllowed = 4;

        int result = minimumShipCapacity(packageWeights, daysAllowed);
        System.out.println("Minimum ship capacity: " + result);
        // Verification: capacity 11 means [3,2], [8], [4,7], [5,1,6] — 4 days ✓

        // Another test case
        int[] smallBatch = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        System.out.println("Minimum capacity for 5 days: " +
            minimumShipCapacity(smallBatch, 5));
        // Answer: 15 (split: [1-5], [6-8], [9-10] ... verifiable)
    }
}