Binary Search Algorithm Tutorial

Binary search is a fast algorithm for finding a target value in a sorted array. Instead of checking every element like linear search at $O(n)$, you repeatedly split the search space in half.

Here's the key insight: if the array is sorted, one comparison tells you which half contains your target. You eliminate $50\%$ of remaining elements each step.

This halving gives you $O(\log n)$ time complexity. For an array of $1$ million elements, you need at most $20$ comparisons instead of $1$ million.

You maintain two pointers: left and right, representing the current search range.

$1.$ Calculate the middle index: mid = left + (right - left) / 2

$2.$ Compare arr[mid] with your target:

• If equal, you found it
• If target is smaller, search the left half: right = mid - 1
• If target is larger, search the right half: left = mid + 1

$3.$ Repeat until left > right (target not found)

Visualize it as a decision tree. Each node is a comparison. You follow one branch and discard the other. The tree height is $\log n$, so that's your worst-case comparisons.

Here's the classic binary search:

function binarySearch(arr, target):
    left = 0
    right = arr.length - 1
    
    while left <= right:
        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

I use left + (right - left) / 2 instead of (left + right) / 2 to prevent integer overflow when left and right are large.

The condition left <= right ensures you check single-element ranges. If you use left < right, you might miss the target when it's the only element left.

Off-by-one errors: Should you set right = mid or right = mid - 1? It depends on your loop condition. With left <= right, use mid - 1 and mid + 1 to avoid infinite loops.

Infinite loops: If left = mid when left + 1 == right, you loop forever. Always ensure your boundaries move.

Wrong return value: When the target doesn't exist, left points to where it would be inserted. This is useful for lower bound searches.

Debugging tip: Print left, right, and mid each iteration. Watch for boundaries that stop moving.