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

package io.thecodeforge.search;

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.");
        }
    }
}

package io.thecodeforge.search;

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);
    }
}

package io.thecodeforge.search;

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)");
    }
}

package io.thecodeforge.search;

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)
        // Java wraps to -1_194_967_296, divided by 2 = -597_483_648
        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; // CORRECT: -1 ensures the window always shrinks
            }
        }
        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("Expected       : 1550000000");

        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));
    }
}

package io.thecodeforge.search;

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("Return value for 50: " + missing);  // negative
        int insertionPoint = -missing - 1;
        System.out.println("50 not found, insertion point: " + insertionPoint);  // 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

        // Missing element in List
        int missingName = Collections.binarySearch(names, "Eve");
        System.out.println("Eve not found, return: " + missingName);  // -(4)-1 = -5
        System.out.println("Eve insertion point: " + (-missingName - 1));  // 4
    }
}

package io.thecodeforge.search;

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;         // record this match
                right = mid - 1;      // keep searching left for earlier occurrence
            } 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;         // record this match
                left = mid + 1;       // keep searching right for later occurrence
            } 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};
        int first = firstOccurrence(duplicates, 2);
        int last = lastOccurrence(duplicates, 2);
        System.out.println("First occurrence of 2: " + first); // 1
        System.out.println("Last occurrence of 2: " + last);   // 3
        System.out.println("Count of 2: " + (last - first + 1)); // 3

        // Edge case: target not present
        System.out.println("First occurrence of 6: " + firstOccurrence(duplicates, 6)); // -1
        System.out.println("Last occurrence of 6: " + lastOccurrence(duplicates, 6));   // -1
    }
}

# ===================== Python =====================
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2  # safe midpoint (no overflow in Python, but good habit)
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Using Python's built-in bisect module (production choice)
import bisect

def binary_search_bisect(arr, target):
    i = bisect.bisect_left(arr, target)
    if i < len(arr) and arr[i] == target:
        return i
    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
print(binary_search_bisect(scores, 63))   # 5
print(binary_search_bisect(scores, 50))   # -1


// ===================== C++ =====================
#include <iostream>
#include <vector>
#include <algorithm>  // for std::lower_bound, std::binary_search

int binarySearch(const std::vector<int>& arr, int target) {
    int left = 0, right = static_cast<int>(arr.size()) - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;  // safe midpoint
        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};

    // Hand-written
    std::cout << "Hand-written: " << binarySearch(scores, 63) << std::endl; // 5
    std::cout << "Hand-written: " << binarySearch(scores, 50) << std::endl; // -1

    // Standard library
    auto it = std::lower_bound(scores.begin(), scores.end(), 63);
    if (it != scores.end() && *it == 63)
        std::cout << "std::lower_bound: index " << (it - scores.begin()) << std::endl; // 5

    bool exists = std::binary_search(scores.begin(), scores.end(), 63);
    std::cout << "std::binary_search: " << (exists ? "found" : "not found") << std::endl;

    return 0;
}

package io.thecodeforge.search;

public class BinarySearchVsLinear {

    // Linear search for small or unsorted 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 — O(log n)
    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) {
        // Build a large sorted array: 0, 2, 4, 6, ..., 1999998
        int[] large = new int[1_000_000];
        for (int i = 0; i < large.length; i++) large[i] = i * 2;

        int target = 999_998; // near the end of the array

        // Warm up JIT
        for (int i = 0; i < 1000; i++) {
            linearSearch(large, target);
            binarySearch(large, target);
        }

        long start, end;

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

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

        // Small array comparison
        int[] small = {1, 3, 5, 7, 9, 11, 13, 15};
        start = System.nanoTime();
        linearSearch(small, 15);
        end = System.nanoTime();
        System.out.println("Linear search on 8 elements:  " + (end - start) + " ns");

        start = System.nanoTime();
        binarySearch(small, 15);
        end = System.nanoTime();
        System.out.println("Binary search on 8 elements:  " + (end - start) + " ns");
    }
}

package io.thecodeforge.search;

/**
 * LeetCode 1011: Capacity To Ship Packages Within D Days
 * Find the smallest ship capacity such that all packages can be shipped within 'days' days.
 * 
 * The feasibility function is monotonic: if capacity C works, any capacity > C also works.
 * This makes it a perfect candidate for binary search on the answer.
 */
public class BinarySearchOnAnswer {

    public int shipWithinDays(int[] weights, int days) {
        // Search space: [max single package weight, total weight of all packages]
        // Minimum capacity must be at least the heaviest package (can't split a package)
        // Maximum capacity is the total weight (ship everything in one day)
        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 (everything in 1 trip)
        }

        // Binary search for the minimum feasible capacity
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (feasible(weights, days, mid)) {
                right = mid;        // mid works — try smaller
            } else {
                left = mid + 1;     // mid doesn't work — need more capacity
            }
        }
        return left; // smallest capacity that works
    }

    /**
     * Can we ship all packages within 'days' days using the given capacity?
     * Greedy: load packages onto the current day until adding the next would exceed capacity.
     */
    private boolean feasible(int[] weights, int days, int capacity) {
        int daysNeeded = 1, currentLoad = 0;
        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysNeeded++;       // start a new day
                currentLoad = 0;
            }
            currentLoad += w;
        }
        return daysNeeded <= days;
    }

    public static void main(String[] args) {
        BinarySearchOnAnswer solver = new BinarySearchOnAnswer();
        int[] weights = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int days = 5;
        int result = solver.shipWithinDays(weights, days);
        System.out.println("Minimum ship capacity for " + days + " days: " + result);
        // Expected: 15 (day1: 1+2+3+4+5=15, day2: 6+7=13, day3: 8, day4: 9, day5: 10)
    }
}

package io.thecodeforge.search;

public class SearchRotatedSortedArray {

    // Search in rotated sorted array (no duplicates) — LeetCode 33
    // Time: O(log n), Space: O(1)
    public static int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;

            // Determine which half is properly sorted
            if (nums[left] <= nums[mid]) {
                // Left half [left..mid] is sorted
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid - 1;  // target is in the sorted left half
                } else {
                    left = mid + 1;   // target must be in the right half
                }
            } else {
                // Right half [mid..right] is sorted
                if (nums[mid] < target && target <= nums[right]) {
                    left = mid + 1;   // target is in the sorted right half
                } else {
                    right = mid - 1;  // target must be in the left half
                }
            }
        }
        return -1;
    }

    // With duplicates — LeetCode 81
    // Worst case O(n) when all elements equal, average O(log n)
    public static boolean searchWithDuplicates(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;

            // Ambiguous case: can't determine which half is sorted
            // Must shrink window linearly — worst case O(n)
            if (nums[left] == nums[mid] && nums[mid] == nums[right]) {
                left++;
                right--;
            } else if (nums[left] <= nums[mid]) {
                if (nums[left] <= target && target < nums[mid]) right = mid - 1;
                else left = mid + 1;
            } else {
                if (nums[mid] < target && target <= nums[right]) left = mid + 1;
                else right = mid - 1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] rotated = {4, 5, 6, 7, 0, 1, 2};
        System.out.println("Search 0 in [4,5,6,7,0,1,2]: index " + search(rotated, 0));  // 4
        System.out.println("Search 3 in [4,5,6,7,0,1,2]: index " + search(rotated, 3));  // -1
        System.out.println("Search 4 in [4,5,6,7,0,1,2]: index " + search(rotated, 4));  // 0
        System.out.println("Search 2 in [4,5,6,7,0,1,2]: index " + search(rotated, 2));  // 6

        int[] withDup = {2, 5, 6, 0, 0, 1, 2};
        System.out.println("Search 0 in [2,5,6,0,0,1,2]: " + searchWithDuplicates(withDup, 0)); // true
        System.out.println("Search 3 in [2,5,6,0,0,1,2]: " + searchWithDuplicates(withDup, 3)); // false
    }
}

// io.thecodeforge — dsa tutorial

public class PreconditionCheck {
    // Real types, not foo/bar
    private static boolean isStrictlySorted(int[] userScores) {
        for (int i = 1; i < userScores.length; i++) {
            if (userScores[i - 1] > userScores[i]) {
                return false;
            }
        }
        return true;
    }

    // O(1) random access check is structural — arrays pass
    public static boolean canBinarySearch(int[] data) {
        return isStrictlySorted(data);
    }
}

// io.thecodeforge — dsa tutorial

public class ComplexityComparison {
    // Iterative binary search — O(log N) time, O(1) space
    public static int searchIterative(int[] data, int target) {
        int low = 0, high = data.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (data[mid] == target) return mid;
            if (data[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    // Just to show call overhead — real search logic above
    public static void main(String[] args) {
        int[] values = {1, 3, 5, 7, 9, 11, 13};
        System.out.println(searchIterative(values, 9)); // 4
        System.out.println(searchIterative(values, 2)); // -1
    }
}

// io.thecodeforge — dsa tutorial

public class BinarySearchSkeleton {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        
        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            if (arr[mid] == target) {
                return mid;
            }
            if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}

// io.thecodeforge — dsa tutorial

import java.util.*;

public class BinarySearchLinksDemo {
    public static void main(String[] args) {
        List<Integer> data = new LinkedList<>();
        for (int i = 0; i < 100000; i++) data.add(i);
        
        // Binary search on LinkedList — O(n), not O(log n)
        int idx = Collections.binarySearch(data, 56789);
        System.out.println("Found at index: " + idx);
        
        // Check why: LinkedList lacks RandomAccess
        System.out.println("RandomAccess? " + 
            (data instanceof RandomAccess));
    }
}

// io.thecodeforge — dsa tutorial

public class BinarySearchVisualization {
    public static int search(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int step = 0;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            System.out.println("Step " + (++step) + ": low=" + low + " high=" + high + " mid=" + mid);
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] data = {2, 5, 8, 12, 19, 27, 33, 42, 50, 61, 73, 88, 95, 100};
        System.out.println("Result index: " + search(data, 42));
    }
}

// io.thecodeforge — dsa tutorial

public class BinarySearchFirstOccurrence {
    public static int first(int[] arr, int target) {
        int low = 0, high = arr.length - 1;
        int result = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] == target) {
                result = mid;
                high = mid - 1;  // keep searching left
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] data = {1, 3, 3, 3, 5, 7, 9};
        System.out.println(first(data, 3));
    }
}