Binary Search

Overview

Binary search is one of the most important algorithms in computer science. It works by comparing the target with the middle element of a sorted array: if the target is smaller, search the left half; if larger, search the right half. Each step eliminates half the remaining elements, giving O(log n) time complexity. For an array of 1 billion elements, binary search needs at most 30 comparisons — that is the power of logarithmic time.

How It Works

1. 1 Start with two pointers: low at the beginning and high at the end of the sorted array.
2. 2 Calculate the middle index: mid = low + (high - low) / 2 (avoids integer overflow vs (low+high)/2).
3. 3 Compare arr[mid] with the target. If equal, return mid.
4. 4 If target < arr[mid], the target must be in the left half — set high = mid - 1.
5. 5 If target > arr[mid], the target must be in the right half — set low = mid + 1.
6. 6 Repeat until low > high (target not found) or the target is found.

When to Use

• →Searching in a sorted array or sorted data structure
• →Finding the boundary in a boolean array (e.g., [False, False, True, True] — find first True)
• →Searching on the answer space (binary search on result: "minimum X such that condition is true")
• →Finding the insertion position for an element
• →Searching in a rotated sorted array

Common Mistakes

• ⚠Using mid = (low + high) / 2 which can overflow for large values — use low + (high - low) / 2
• ⚠Off-by-one errors with the boundaries (low = mid vs low = mid + 1)
• ⚠Forgetting to handle the case where the target is not in the array
• ⚠Not sorting the array before applying binary search
• ⚠Using binary search on unsorted data (it only works on sorted data or monotonic predicates)

Code Examples

int binarySearch(int[] arr, int target) {
    int low = 0, high = arr.length - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // not found
}

int binarySearch(vector<int>& arr, int target) {
    int low = 0, high = arr.size() - 1;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (arr[mid] == target) return mid;
        else if (arr[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1; // not found
}

def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1  # not found

function binarySearch(arr, target) {
  let low = 0, high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1; // not found
}

Related Patterns

Practice Problems

Frequently Asked Questions