The Art of Binary Search

Imagine you're looking up a word in a printed dictionary. You don't start at page one and read every word until you find it. Instead, you open the book to the middle. If your word comes earlier, you ignore the entire right half of the book. If it comes later, you discard the left half. You repeat this process until you land on the exact page.

This great strategy is called binary search. It's a fundamental algorithm used to find the position of a target value within a sorted array.

By cutting your search space in half with every single step, binary search achieves a logarithmic time complexity.

One Little Thing

For binary search to work, your data must be sorted. If the data is randomized, the algorithm won't work.

Two Ways to Define Boundaries

You've got to decide how to track your boundaries using two pointers: left and right. Devs generally choose between two standard approaches: the inclusive upper bound and the exclusive upper bound.

While both ways get the job done, they change your loop conditions and how you drop halves of the array.

Approach 1: The Inclusive Upper Bound

In this traditional version, the right pointer targets the last valid index of the array. The search window includes both boundary pointers.

1. Setup and Loop Condition

You start by setting left = 0 and right = arr.length - 1. The loop repeats as long as left <= right. If the pointers cross (left > right), it means the target item isn't in the array. You should return a specific value (e.g. -1) to signal that nothing was found.

2. Shifting the Boundaries

After calculating mid = left + Math.floor((right - left) / 2), you compare arr[mid] to your target:

• The Match: If arr[mid] == target, you return mid.

• Drop the Right Side: If arr[mid] > target, the target is to the left. You update the boundary to right = mid - 1.

• Drop the Left Side: If arr[mid] < target, the target is to the right. You update the boundary to left = mid + 1.

3. Simple Code Example (Don't use for all cases)

function binarySearchInclusive(arr, target) {
    let left = 0;
    let right = arr.length - 1; 

    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);

        if (arr[mid] === target) {
            return mid; 
        } else if (arr[mid] > target) {
            right = mid - 1; 
        } else {
            left = mid + 1;  
        }
    }

    return -1;
}

We calculate the mid index using left + Math.floor((right - left) / 2) because doing standard addition (left + right) in languages like Java or C++ can overflow the maximum 32-bit integer limit if you are searching through massive datasets. This formula keeps your code 100% safe across all environments.

Approach 2: The Exclusive Upper Bound

In this version, the right pointer represents the index just past the last element you want to search. The search window includes left but excludes right.

1. Setup and Loop Condition

You initialize left = 0 and set right = arr.length (the exact length of the array).

Because right is exclusive, a search space where left == right represents an empty range. Therefore, your loop condition changes to left < right. Once left equals right, the loop exits, signaling the item wasn't found.

2. Shifting the Boundaries

The main change is how right is treated. If arr[mid] > target, you drop the right half by setting right = mid. You don't use mid - 1 since the upper bound is exclusive.

3. Simple Code Example (Once again, don't use for all cases)

function binarySearchExclusive(arr, target) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        const mid = left + Math.floor((right - left) / 2);

        if (arr[mid] === target) {
            return mid; 
        } else if (arr[mid] > target) {
            right = mid; 
        } else {
            left = mid + 1; 
        }
    }

    return -1;
}

When to Use Each?

• Inclusive Upper Bound: Use this version when you're looking for a single, exact match in a sorted array and want to return its index immediately.

• Exclusive Upper Bound: Use this version when you want to find the first occurrence of a number in an array full of duplicates or you want to insert a new number while keeping the array sorted.

Why Binary Search is a Superpower

Imagine you've got an array of 1 million items.

• Linear Search: Could take up to 1,000,000 steps if you're trying to find an item at the very end of the array.
• Binary Search: Will find any item in roughly 20 steps.

Every time you use a drop formula, you wipe out thousands of unnecessary checks. It transforms a massive data search into a quick handful of simple choices.