Binary Search

How Binary Search Works

Binary search operates on a sorted array. The core idea is simple: instead of scanning every element one by one (linear search), we compare the target with the middle element and discard half of the remaining elements in a single step.

The algorithm maintains two pointers, low and high, that define the current search range. At each iteration it:

Computes mid = floor((low + high) / 2).
If arr[mid] equals the target, the search is complete.
If arr[mid] is less than the target, the target must lie in the right half, so set low = mid + 1.
If arr[mid] is greater than the target, the target must lie in the left half, so set high = mid - 1.

This halving continues until the target is found or low > high, meaning the element is not present. Because the search space is halved each time, binary search runs in O(log n) time — dramatically faster than linear search for large datasets.

Key prerequisite: The array must be sorted before binary search can be applied. If the data is unsorted, you must sort it first (or use a different search strategy).

Interactive Visualization

Watch binary search in action. The blue arrow marks low, the yellow arrow marks mid, and the red arrow marks high. Eliminated regions are greyed out, and a found element glows green.

Set a target and click Search to begin.

Speed No steps

Target:

Code Implementation

Below is the iterative implementation of binary search in three languages. The iterative version is preferred in practice because it uses O(1) extra space and avoids the overhead of recursive function calls.

def binary_search(arr, target):
    """Return the index of target in sorted arr, or -1 if not found."""
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid          # Target found
        elif arr[mid] < target:
            low = mid + 1       # Search right half
        else:
            high = mid - 1      # Search left half

    return -1                   # Target not in array


# Example usage
nums = [2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91]
result = binary_search(nums, 23)
print(f"Found at index: {result}")  # Output: Found at index: 5

public class BinarySearch {
    /**
     * Returns the index of target in sorted array, or -1 if not found.
     */
    public static int binarySearch(int[] arr, int target) {
        int low = 0;
        int high = arr.length - 1;

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

            if (arr[mid] == target) {
                return mid;             // Target found
            } else if (arr[mid] < target) {
                low = mid + 1;          // Search right half
            } else {
                high = mid - 1;         // Search left half
            }
        }

        return -1;                      // Target not in array
    }

    public static void main(String[] args) {
        int[] nums = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
        int result = binarySearch(nums, 23);
        System.out.println("Found at index: " + result);  // Output: 5
    }
}

#include <iostream>
#include <vector>
using namespace std;

/**
 * Returns the index of target in sorted vector, or -1 if not found.
 */
int binarySearch(const vector<int>& arr, int target) {
    int low = 0;
    int high = static_cast<int>(arr.size()) - 1;

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

        if (arr[mid] == target) {
            return mid;             // Target found
        } else if (arr[mid] < target) {
            low = mid + 1;          // Search right half
        } else {
            high = mid - 1;         // Search left half
        }
    }

    return -1;                      // Target not in array
}

int main() {
    vector<int> nums = {2, 5, 8, 12, 16, 23, 38, 45, 56, 72, 91};
    int result = binarySearch(nums, 23);
    cout << "Found at index: " << result << endl;  // Output: 5
    return 0;
}

Complexity Analysis

Binary search is remarkably efficient. Each comparison eliminates half of the remaining candidates, yielding a logarithmic number of steps. The iterative version requires only a constant amount of extra memory for the three pointer variables.

Case	Time Complexity	Space Complexity	Description
Best	O(1)	O(1)	Target is at the midpoint on the first comparison
Average	O(log n)	O(1)	Target is found after halving the search space several times
Worst	O(log n)	O(1)	Target is at the boundary or not present; all halving steps are needed

For an array of 1,000,000 elements, binary search needs at most about 20 comparisons (log₂ 1,000,000 ≈ 20), compared to up to 1,000,000 comparisons for linear search. This makes binary search the standard choice for searching in sorted collections.

Practice Problems

Strengthen your understanding of binary search by solving these classic problems:

Easy Binary Search LeetCode #704

Easy Search Insert Position LeetCode #35

Medium Find First and Last Position of Element in Sorted Array LeetCode #34

Quiz

Test your knowledge of binary search with these questions.

Q1. What is the primary prerequisite for binary search to work correctly?

The array must contain unique elements

The array must be sorted

The array must have an even number of elements

The array must be stored in contiguous memory

Binary search requires the input to be sorted so that it can reliably eliminate half of the remaining elements at each step. The algorithm compares the middle element with the target and decides which half to discard based on the sorted ordering. Duplicate elements, array size parity, and memory layout do not affect correctness.

Q2. What is the worst-case time complexity of binary search on an array of n elements?

O(n)

O(n log n)

O(log n)

O(1)

In the worst case, binary search halves the search space until only one element remains, which takes log₂(n) comparisons. O(1) is the best case (element at the midpoint immediately), and O(n) would be linear search.

Q3. In Java/C++, why is mid = low + (high - low) / 2 preferred over mid = (low + high) / 2?

It is faster to compute

It avoids integer overflow when low + high exceeds the maximum integer value

It produces a different midpoint that is more accurate

It works on unsorted arrays as well

When low and high are both large positive integers, their sum can exceed Integer.MAX_VALUE (2³¹ - 1), causing integer overflow and producing a negative midpoint. The formula low + (high - low) / 2 computes the same result without adding the two large numbers together, preventing the overflow.

Q4. Given the sorted array [3, 7, 11, 15, 19, 23, 27], how many comparisons does binary search need to find the value 19?

2

3

4

1

Trace through the algorithm: (1) low=0, high=6, mid=3 → arr[3]=15 < 19, so low=4. (2) low=4, high=6, mid=5 → arr[5]=23 > 19, so high=4. (3) low=4, high=4, mid=4 → arr[4]=19 == 19, found! That is 3 comparisons total. Each iteration performs exactly one comparison against the target.

Q5. Which of the following is NOT a valid application of binary search?

Finding an element in a sorted array

Finding the square root of a number to a given precision

Finding the insertion point in a sorted array

Finding the maximum element in an unsorted array