I remember a junior developer on my team a few years ago who was debugging a latency spike in our ledger service. He had written a simple loop to find a specific transaction ID in a list of a few million records. It worked perfectly in staging with 1,000 records, but in production, the API response time climbed to several seconds. When I looked at the code, I saw a classic linear search: he was checking every single element from index 0 until he found a match. The problem was that the list was already sorted, but he wasn't taking advantage of it. We switched him to a binary search, and the search time dropped from milliseconds to practically instantaneous.

The Logic of Divide and Conquer

Binary search is essentially the "phone book" method of searching. If you're looking for a name starting with 'M', you don't start at page one; you open the book to the middle. If you land on 'P', you know 'M' must be in the left half, so you throw the right half away and repeat the process with the remaining pages.

In Java, we implement this using three pointers: low, high, and mid. As long as low is less than or equal to high, we calculate the middle index. If the element at mid is our target, we're done. If the target is smaller, we move the high pointer to mid - 1. If it's larger, we move the low pointer to mid + 1. This effectively cuts the search area in half with every single iteration, giving us a time complexity of O(log n).

public int binarySearch(int[] numbers, int target) {
    int low = 0;
    int high = numbers.length - 1;

    while (low <= high) {
        int mid = low + (high - low) / 2;

        if (numbers[mid] == target) {
            return mid; // Target found!
        } else if (numbers[mid] < target) {
            low = mid + 1; // Target is in the right half
        } else {
            high = mid - 1; // Target is in the left half
        }
    }
    return -1; // Target not found
}

Avoiding the Integer Overflow Trap

You might have noticed I wrote int mid = low + (high - low) / 2; instead of the more intuitive (low + high) / 2. In a classroom setting, both work. In a production environment with massive arrays, the second one can crash your program.

Here is why: low and high are integers. If you have a truly giant array and both low and high are very large, adding them together can exceed the maximum value of a 32-bit signed integer (2,147,483,647). This causes an integer overflow, resulting in a negative number, which then leads to an ArrayIndexOutOfBoundsException. By subtracting low from high first, we ensure the value stays within the safe range. It's a small detail, but it's the kind of thing that separates a senior engineer from a beginner.

📋 Practical Task

Implementing a Sorted Product SKU Lookup

You are building a warehouse management system where product SKUs (stored as integers) are kept in a sorted array for fast retrieval. Your task is to implement a method that finds the index of a specific SKU. If the SKU does not exist in the array, the method should return -1.

Requirements:

• Create a class WarehouseSearch with a method public int findSku(int[] skus, int targetSku).
• Implement the binary search algorithm to ensure the lookup is O(log n).
• Use the overflow-safe method for calculating the middle index.
• Test your implementation with an array like {1001, 1005, 1010, 1020, 1050, 1100} and search for both an existing SKU (e.g., 1020) and a non-existent one (e.g., 1015).