Binary Search Overflow — The Bug Hidden in Java for 9 Years

public class LinearSearchExample {

    // Check every element one-by-one until we find the target
    public static int findWithLinearSearch(int[] sortedScores, int targetScore) {
        for (int index = 0; index < sortedScores.length; index++) {
            // Did we find the target at this position?
            if (sortedScores[index] == targetScore) {
                return index; // Return the position where it was found
            }
        }
        return -1; // -1 is the convention for "not found"
    }

    public static void main(String[] args) {
        int[] sortedScores = {10, 22, 35, 47, 58, 63, 79, 81, 94, 99};
        int targetScore = 79;

        int result = findWithLinearSearch(sortedScores, targetScore);

        if (result != -1) {
            System.out.println("Score " + targetScore + " found at index " + result);
            System.out.println("Linear search checked " + (result + 1) + " element(s) to get there.");
        } else {
            System.out.println("Score " + targetScore + " was not found.");
        }
    }
}

public class BinarySearchIterative {

    /**
     * Searches for targetScore inside a sorted array using binary search.
     * Returns the index of the target if found, or -1 if not present.
     */
    public static int binarySearch(int[] sortedScores, int targetScore) {
        int leftBoundary = 0;                        // Start of the search window
        int rightBoundary = sortedScores.length - 1; // End of the search window
        int stepCount = 0;                           // Just for demonstration

        while (leftBoundary <= rightBoundary) {
            stepCount++;

            // Calculate midpoint — see the Gotchas section for WHY we write it this way
            int middleIndex = leftBoundary + (rightBoundary - leftBoundary) / 2;
            int middleValue = sortedScores[middleIndex];

            System.out.println("Step " + stepCount + ": Checking index " + middleIndex
                    + " (value = " + middleValue + ")  |  window: ["
                    + leftBoundary + ", " + rightBoundary + "]");

            if (middleValue == targetScore) {
                // Bullseye — target is right here
                System.out.println("Found " + targetScore + " at index "
                        + middleIndex + " in " + stepCount + " step(s).\n");
                return middleIndex;

            } else if (middleValue < targetScore) {
                // Middle value is too small — target must be in the RIGHT half
                leftBoundary = middleIndex + 1;

            } else {
                // Middle value is too big — target must be in the LEFT half
                rightBoundary = middleIndex - 1;
            }
        }

        // Left has crossed right — target is not in the array
        System.out.println(targetScore + " was not found after " + stepCount + " step(s).\n");
        return -1;
    }

    public static void main(String[] args) {
        int[] sortedScores = {10, 22, 35, 47, 58, 63, 79, 81, 94, 99};

        System.out.println("--- Searching for 63 ---");
        binarySearch(sortedScores, 63);

        System.out.println("--- Searching for 50 (not in array) ---");
        binarySearch(sortedScores, 50);

        System.out.println("--- Searching for 10 (first element) ---");
        binarySearch(sortedScores, 10);
    }
}

public class BinarySearchRecursive {

    /**
     * Recursive binary search.
     * Each call works on a shrinking window defined by leftBoundary and rightBoundary.
     */
    public static int binarySearchRecursive(
            int[] sortedTemperatures,
            int targetTemp,
            int leftBoundary,
            int rightBoundary) {

        // Base case: the window is empty — target is not in the array
        if (leftBoundary > rightBoundary) {
            return -1;
        }

        // Find the midpoint of the current window
        int middleIndex = leftBoundary + (rightBoundary - leftBoundary) / 2;
        int middleValue = sortedTemperatures[middleIndex];

        if (middleValue == targetTemp) {
            // Found it — return the position
            return middleIndex;

        } else if (middleValue < targetTemp) {
            // Target is in the right half — recurse with updated left boundary
            return binarySearchRecursive(
                    sortedTemperatures, targetTemp, middleIndex + 1, rightBoundary);

        } else {
            // Target is in the left half — recurse with updated right boundary
            return binarySearchRecursive(
                    sortedTemperatures, targetTemp, leftBoundary, middleIndex - 1);
        }
    }

    // Convenience wrapper so the caller doesn't need to pass initial boundaries
    public static int search(int[] sortedTemperatures, int targetTemp) {
        return binarySearchRecursive(
                sortedTemperatures, targetTemp, 0, sortedTemperatures.length - 1);
    }

    public static void main(String[] args) {
        int[] weeklyHighTemps = {-5, 0, 3, 7, 12, 18, 21, 26, 30};

        int searchTarget = 18;
        int foundAt = search(weeklyHighTemps, searchTarget);

        if (foundAt != -1) {
            System.out.println("Temperature " + searchTarget
                    + "°C found at index " + foundAt);
        } else {
            System.out.println("Temperature " + searchTarget + "°C not in records.");
        }

        // Try a value that doesn't exist
        int missingTemp = 15;
        int missingResult = search(weeklyHighTemps, missingTemp);
        System.out.println("Temperature " + missingTemp
                + "°C found at index: " + missingResult
                + " (−1 means not found)");
    }
}

public class BinarySearchPitfalls {

    // ============================================================
    // MISTAKE 1: Integer overflow when calculating the midpoint
    // ============================================================

    public static int buggyMidpoint(int left, int right) {
        // WRONG: (left + right) can overflow if both are large integers
        // e.g. left = 1_500_000_000, right = 1_600_000_000
        // Their sum = 3_100_000_000 which exceeds Integer.MAX_VALUE (2_147_483_647)
        return (left + right) / 2; // <-- DANGER ZONE
    }

    public static int safeMidpoint(int left, int right) {
        // CORRECT: This formula gives the same result but never overflows
        // because we add a small delta (right - left) to left, not two large numbers
        return left + (right - left) / 2; // <-- SAFE
    }

    // ============================================================
    // MISTAKE 2: Infinite loop from wrong boundary update
    // ============================================================

    public static int binarySearchWithInfiniteLoopBug(int[] sorted, int target) {
        int left = 0;
        int right = sorted.length - 1;

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

            if (sorted[mid] == target) return mid;

            else if (sorted[mid] < target) {
                left = mid; // WRONG: should be mid + 1
                // When left = 2, right = 3, mid = 2
                // We set left = 2 again — nothing changes — infinite loop!
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static int binarySearchFixed(int[] sorted, int target) {
        int left = 0;
        int right = sorted.length - 1;

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

            if (sorted[mid] == target) return mid;

            else if (sorted[mid] < target) {
                left = mid + 1; // CORRECT: +1 ensures the window always shrinks
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println("=== Midpoint Calculation ===");
        int largeLeft = 1_500_000_000;
        int largeRight = 1_600_000_000;
        System.out.println("Buggy midpoint : " + buggyMidpoint(largeLeft, largeRight));
        System.out.println("Safe  midpoint : " + safeMidpoint(largeLeft, largeRight));

        System.out.println("\n=== Fixed Binary Search ===");
        int[] prices = {5, 12, 19, 27, 34, 41, 55, 68};
        System.out.println("Search for 34: index " + binarySearchFixed(prices, 34));
        System.out.println("Search for 99: index " + binarySearchFixed(prices, 99));
    }
}

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BinarySearchBuiltInExample {
    public static void main(String[] args) {
        // Arrays.binarySearch for int[]
        int[] scores = {10, 22, 35, 47, 58, 63, 79, 81, 94, 99};
        int index = Arrays.binarySearch(scores, 63);
        System.out.println("Found 63 at index: " + index);  // 5
        
        // Negative return for missing value
        int missing = Arrays.binarySearch(scores, 50);
        System.out.println("50 not found, insertion point: " + (-missing - 1));  // insertion point = 4
        
        // Collections.binarySearch for List
        List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "Diana");
        int charlieIndex = Collections.binarySearch(names, "Charlie");
        System.out.println("Charlie at index: " + charlieIndex);  // 2
    }
}

public class FirstLastOccurrence {

    // Returns index of first occurrence of target (leftmost)
    public static int firstOccurrence(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                right = mid - 1;  // keep searching left
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    // Returns index of last occurrence of target (rightmost)
    public static int lastOccurrence(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        int result = -1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) {
                result = mid;
                left = mid + 1;   // keep searching right
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] duplicates = {1, 2, 2, 2, 3, 4, 4, 5};
        System.out.println("First occurrence of 2: " + firstOccurrence(duplicates, 2)); // 1
        System.out.println("Last occurrence of 2: " + lastOccurrence(duplicates, 2));   // 3
        System.out.println("Count of 2: " + (lastOccurrence(duplicates, 2) - firstOccurrence(duplicates, 2) + 1)); // 3
    }
}

# Python implementation
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example usage
scores = [10, 22, 35, 47, 58, 63, 79, 81, 94, 99]
print(binary_search(scores, 63))  # 5
print(binary_search(scores, 50))  # -1

// C++ implementation
#include <iostream>
#include <vector>

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = arr.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

int main() {
    std::vector<int> scores = {10, 22, 35, 47, 58, 63, 79, 81, 94, 99};
    std::cout << binarySearch(scores, 63) << std::endl; // 5
    std::cout << binarySearch(scores, 50) << std::endl; // -1
    return 0;
}

package io.thecodeforge.search;

public class BinarySearchVsLinear {

    // Linear search for small arrays — simpler, cache-friendly
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }

    // Binary search for large sorted arrays
    public static int binarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        // Decision helper: search strategy depends on size and sort status
        int[] small = {1, 3, 5, 7, 9};
        int[] large = new int[1000000];
        for (int i = 0; i < large.length; i++) large[i] = i * 2;

        long start, end;
        start = System.nanoTime();
        linearSearch(large, 999998);
        end = System.nanoTime();
        System.out.println("Linear on 1M: " + (end - start) + " ns");

        start = System.nanoTime();
        binarySearch(large, 999998);
        end = System.nanoTime();
        System.out.println("Binary on 1M: " + (end - start) + " ns");
    }
}

// Find the smallest capacity such that packages can be shipped within D days
public class BinarySearchOnAnswer {
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int w : weights) {
            left = Math.max(left, w);  // at least the heaviest package
            right += w;                 // at most total weight
        }
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (feasible(weights, days, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    private boolean feasible(int[] weights, int days, int capacity) {
        int daysNeeded = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return daysNeeded <= days;
    }
}