Binary Search Algorithm — O(log n) Search Guide

Binary Search

Binary Search is an efficient searching algorithm used to find an element in a sorted array or sorted list. Instead of checking every element one by one, it repeatedly cuts the search space into two halves.

Because half of the remaining elements are discarded at every step, binary search is much faster than linear search for large sorted data sets.

Why Binary Search Is Fast

The strength of binary search comes from elimination. After one comparison, half of the remaining elements are ignored. After another comparison, half of what remains is ignored again.

For example, if an array has 1,024 elements:

• After 1 step, only 512 remain.
• After 2 steps, only 256 remain.
• After 10 steps, only 1 element remains.

That is why binary search has logarithmic time complexity.

Main Requirement

Binary search works correctly only when the data is sorted.

• If the array is sorted in ascending order, the normal form of binary search can be used directly.
• If the array is unsorted, binary search cannot reliably decide which half to discard.

Core Idea

At each step:

• Find the middle element.
• If the middle element matches the target, return the answer.
• If the target is smaller, continue searching in the left half.
• If the target is larger, continue searching in the right half.

This is a classic divide and conquer algorithm because each step reduces the problem from size n to roughly n / 2.

When to Prefer Binary Search

• When the data is already sorted.
• When many searches must be performed on the same sorted collection.
• When the input size is large enough that linear search becomes expensive.
• When the problem has a monotonic condition and can be solved using answer-space binary search.

Step-by-Step Algorithm

1. Initialize low = 0 and high = n - 1.
2. While low <= high, compute the middle index.
3. If arr[mid] == target, return mid.
4. If arr[mid] < target, move to the right half by setting low = mid + 1.
5. If arr[mid] > target, move to the left half by setting high = mid - 1.
6. If the loop ends, the element is not present, so return -1.

Time and Space Complexity

Iterative Binary Search

The iterative version is usually preferred because it is simple and uses constant extra space.

public class BinarySearchIterative {

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

Recursive Binary Search

The recursive version expresses the divide-and-conquer idea more directly, but it uses extra stack space.

public class BinarySearchRecursive {

    static int binarySearch(int[] arr, int low, int high, int target) {
        if (low > high) {
            return -1;
        }

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

        if (arr[mid] == target) {
            return mid;
        }

        if (arr[mid] < target) {
            return binarySearch(arr, mid + 1, high, target);
        }

        return binarySearch(arr, low, mid - 1, target);
    }
}

Why Use `mid = low + (high - low) / 2`?

Instead of writing (low + high) / 2, many implementations use:

mid = low + (high - low) / 2

This avoids possible integer overflow when low + high becomes too large.

Dry Run Strategy

When solving binary search questions by hand, follow this order:

• Write the current low and high.
• Compute mid.
• Compare arr[mid] with the target.
• Decide which half can be discarded.
• Repeat until the range becomes empty or the answer is found.

Trace Example

Suppose:

arr = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19} and target = 7

If the Element Is Not Present

Binary search ends when low becomes greater than high. This means there is no valid search interval left, so the target does not exist in the array.

This stopping condition is very important. Without it, the loop or recursion may continue incorrectly.

Binary Search Variants

Binary search is not limited to exact search. Many common interview and algorithm problems are based on its variants.

First and Last Occurrence

When duplicates are present, normal binary search may return any matching index. To find the first or last occurrence, continue the search even after a match is found.

public class BinarySearchOccurrences {

    static int firstOccurrence(int[] arr, int target) {
        int low = 0;
        int 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;
            } else if (arr[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return result;
    }

    static int lastOccurrence(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;
        int result = -1;

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

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

        return result;
    }
}

Binary Search on Answer Space

Sometimes we do not search for an array element at all. Instead, we search over a range of possible answers. This works when the condition is monotonic, meaning that once a certain value works, all larger values also work, or all smaller values also work.

public class SqrtBinarySearch {

    static long sqrt(long n) {
        if (n < 2) {
            return n;
        }

        long low = 1;
        long high = n / 2;
        long result = 1;

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

            if (mid * mid == n) {
                return mid;
            }

            if (mid * mid < n) {
                result = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }

        return result;
    }
}

Binary Search vs Linear Search

Common Interview Patterns

• Find the first or last occurrence of an element in a sorted array.
• Count duplicates in sorted data.
• Find a missing number or insertion position.
• Search in a rotated sorted array.
• Find the minimum feasible or maximum feasible answer using a monotonic condition.

Common Mistakes in Binary Search

• Using binary search on an unsorted array.
• Updating the boundaries incorrectly and creating an infinite loop.
• Using the wrong loop condition.
• Returning immediately when a first or last occurrence is actually required.
• Using (low + high) / 2 carelessly in languages where overflow matters.
• Forgetting whether the search interval is inclusive or exclusive.

Key Takeaways

• Binary search is an efficient search technique for sorted data.
• Its speed comes from eliminating half of the remaining search space at every step.
• It cuts the search space in half at every step.
• Its average and worst-case time complexity is O(log n).
• Iterative binary search uses O(1) extra space, while recursive binary search uses O(log n) stack space.
• Binary search has many useful variants, including first occurrence, last occurrence, floor, ceiling, and answer-space search.