Binary Search

Introduction

Binary search is a classic algorithm used to quickly find the position of a target value within a sorted collection. It repeatedly divides the search interval in half, discarding the half that cannot contain the target. Because of this halving behavior, binary search runs in logarithmic time: O(log n).

If you are new to complexity analysis, review our guide to Big-O Notation. Also see our overview of Arrays, since binary search is most commonly applied to sorted arrays.

When to use binary search

Use binary search when:

1. Your data is already sorted, or you can afford to sort it once and then perform many searches.
2. You need fast lookups with minimal extra memory.
3. You are searching in a space where you can define an ordering and midpoints (e.g., numbers, strings, or even an implicit search space like answer ranges in optimization problems).

Avoid binary search when:

• The data changes frequently (insertions/deletions) and maintaining sorted order is costly.
• You need average-case O(1) lookups with frequent updates; a hash table might be a better fit.

How it works (high level)

1. Start with two pointers: left at the beginning and right at the end of the array.
2. Compute mid = floor((left + right) / 2).
3. Compare arr[mid] with the target:
   • If equal, return mid.
   • If arr[mid] is less than target, search the right half (left = mid + 1).
   • Otherwise, search the left half (right = mid - 1).
4. Repeat until left passes right. If not found, return a sentinel (e.g., -1).

Iterative implementation

Below are iterative implementations in three languages. All return the index of target if found, or -1 if not found.

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

// Example usage
const arr = [2, 5, 7, 10, 13, 18, 21];
console.log(binarySearch(arr, 10)); // 3
console.log(binarySearch(arr, 4));  // -1

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

# Example usage
arr = [2, 5, 7, 10, 13, 18, 21]
print(binary_search(arr, 10))  # 3
print(binary_search(arr, 4))   # -1

public class BinarySearch {
    public static int search(int[] arr, int target) {
        int left = 0, right = arr.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2; // avoids overflow
            if (arr[mid] == target) return mid;
            if (arr[mid] < target) left = mid + 1; else right = mid - 1;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 5, 7, 10, 13, 18, 21};
        System.out.println(search(arr, 10)); // 3
        System.out.println(search(arr, 4));  // -1
    }
}

Recursive implementation

Binary search can also be implemented recursively. While concise, be mindful of recursion depth for extremely large inputs.

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) return -1;
  const mid = Math.floor((left + right) / 2);
  if (arr[mid] === target) return mid;
  if (arr[mid] < target) return binarySearchRecursive(arr, target, mid + 1, right);
  return binarySearchRecursive(arr, target, left, mid - 1);
}

def binary_search_recursive(arr, target, left=0, right=None):
    if right is None:
        right = len(arr) - 1
    if left > right:
        return -1
    mid = (left + right) // 2
    if arr[mid] == target:
        return mid
    if arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)
    return binary_search_recursive(arr, target, left, mid - 1)

public class RecursiveBinarySearch {
    public static int search(int[] arr, int target) {
        return helper(arr, target, 0, arr.length - 1);
    }
    private static int helper(int[] arr, int target, int left, int right) {
        if (left > right) return -1;
        int mid = left + (right - left) / 2;
        if (arr[mid] == target) return mid;
        if (arr[mid] < target) return helper(arr, target, mid + 1, right);
        return helper(arr, target, left, mid - 1);
    }
}

Complexity

• Time complexity: O(log n) comparisons in the worst and average cases.
• Space complexity:
  • Iterative: O(1) additional space.
  • Recursive: O(log n) due to call stack depth.

Common pitfalls and edge cases

• Unsorted input: Always ensure the array is sorted in the same order you’re searching.
• Overflow in midpoint calculation: In languages with fixed-width integers, compute mid as left + (right - left) / 2 to avoid overflow.
• Duplicates: If the array contains duplicates and you need the first or last occurrence, adjust the algorithm to continue searching even after finding a match.
• Off-by-one errors: Carefully verify loop conditions (left <= right) and updates to left/right.

Variations

Binary search is more than a lookup algorithm. It’s a technique that appears in many problems:

• Searching for the first/last occurrence of a value.
• Finding lower_bound/upper_bound (first element >= target, first element > target).
• Searching answers in a monotonic predicate space (a.k.a. “binary search on answer”).

Practice prompts

Try implementing these variations:

1. Return the index of the first occurrence of target in a sorted array with duplicates.
2. Given a sorted array, return the index where target should be inserted to keep the array sorted.
3. Given isPossible(x) that returns true if x is possible and false otherwise, find the smallest x that is possible within a range.