How Binary Search Works

Go back to the phone book from Day 2. You're looking for "Martinez." You don't start at "Aaron" and read forward — you flip to the middle, land somewhere around "M," and instantly know whether to search the front half or the back half. Then you do it again on that half. And again. In about 20 flips, you've searched a phone book with a million names. That instinct — cut the problem in half, every single step — is Binary Search, and it's the clearest possible demonstration of why O(log n) beats O(n) so dramatically.

The One Requirement: Sorted Data

Binary Search only works if the array is already sorted. That sorted order is what lets you safely eliminate half the remaining elements with a single comparison — without it, there's no way to know which half your target is in, and you're back to checking everything with Linear Search.

How Binary Search Works

1. Look at the middle element of the array.
2. If it matches the target, you're done.
3. If the target is smaller, repeat the search on the left half only.
4. If the target is larger, repeat the search on the right half only.
5. Keep narrowing until you find the target or the range is empty.

Walking Through an Example

Search for 23 in the sorted array [4, 8, 15, 16, 23, 42]:

• Range is index 0–5. Middle is index 2: 15. 23 > 15, so search the right half.
• Range is now index 3–5. Middle is index 4: 23. Match! Return index 4.

Two comparisons found the answer in a 6-element array. Linear Search would have needed up to five. That gap only gets wider as the array grows — that's the entire point of logarithmic time.

Java Implementation

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

        while (low <= high) {
            // Avoids integer overflow compared to (low + high) / 2
            int mid = low + (high - low) / 2;

            if (arr[mid] == target) {
                return mid; // found it
            } else if (arr[mid] < target) {
                low = mid + 1; // target must be in the right half
            } else {
                high = mid - 1; // target must be in the left half
            }
        }
        return -1; // not found
    }

    public static void main(String[] args) {
        int[] arr = {4, 8, 15, 16, 23, 42};
        System.out.println(binarySearch(arr, 23)); // Output: 4
        System.out.println(binarySearch(arr, 99)); // Output: -1
    }
}

📝 Note

mid = low + (high - low) / 2 instead of (low + high) / 2 is a small but genuinely important detail — with very large arrays, low + high can overflow a 32-bit int. Interviewers notice when you know this.

Recursive Version

Binary Search also has a clean recursive form, which is worth knowing since it's a common way interviewers ask for it:

public static int binarySearchRecursive(int[] arr, int target, int low, int high) {
    if (low > high) {
        return -1; // search space exhausted, not found
    }

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

    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, high);
    } else {
        return binarySearchRecursive(arr, target, low, mid - 1);
    }
}

Time Complexity

⚠️ Complexity Breakdown

Best case: O(1) — the target is the first middle element checked.
Average case: O(log n)
Worst case: O(log n)
Space: O(1) iterative, O(log n) recursive (due to the call stack).

💡 Tip

That O(log n) is genuinely dramatic at scale: searching 1,000,000 sorted elements takes at most about 20 comparisons. Double the array to 2,000,000, and it only costs one more comparison. That's the defining property of logarithmic growth.

Common Interview Questions

• Why does Binary Search require sorted input, and what happens if you run it on unsorted data?
• What's the time complexity of Binary Search, and why does doubling the input size barely change the number of steps?
• How would you find the first or last occurrence of a duplicate value using a modified Binary Search?
• Why might the iterative version be preferred over the recursive one in production code?

The Takeaway

Binary Search is proof that knowing one extra fact about your data — that it's sorted — can turn an O(n) problem into an O(log n) one. That "use what you know about the data" mindset is exactly what powers the next few searches in this series: Jump Search, Interpolation Search, and Exponential Search all take that same idea and specialize it further for particular situations.

➡️ Next in the Series

Jump Search: A Middle Ground Between Linear and Binary Search

Happy learning!
— Team CodeElevateX 🚀