Binary Search

Category: Classical
Difficulty: Beginner
Time Complexity: O(log n)
Space Complexity: O(1)

Overview

Binary search is a divide-and-conquer algorithm that finds a target value in a sorted array. At each step, it compares the target with the middle element and eliminates half of the remaining search space. This gives it O(log n) time complexity — dramatically faster than linear search for large arrays. Binary search is one of the most fundamental algorithms in computer science and appears everywhere from database indexing to debugging (git bisect).

Try It

• Web: Open in Eigenvue →
• Python:

  import eigenvue
  eigenvue.show("binary-search")

Default Inputs

{
  "array": [
    1,
    3,
    5,
    7,
    9,
    11,
    13,
    15,
    17,
    19
  ],
  "target": 13
}

Input Examples

Default (target found)

{
  "array": [
    1,
    3,
    5,
    7,
    9,
    11,
    13,
    15,
    17,
    19
  ],
  "target": 13
}

Target not found

{
  "array": [
    2,
    4,
    6,
    8,
    10,
    12,
    14
  ],
  "target": 5
}

Single element (found)

{
  "array": [
    42
  ],
  "target": 42
}

Single element (not found)

{
  "array": [
    42
  ],
  "target": 99
}

Target is first element

{
  "array": [
    1,
    3,
    5,
    7,
    9,
    11,
    13
  ],
  "target": 1
}

Target is last element

{
  "array": [
    1,
    3,
    5,
    7,
    9,
    11,
    13
  ],
  "target": 13
}

Large array

{
  "array": [
    2,
    5,
    8,
    11,
    14,
    17,
    20,
    23,
    26,
    29,
    32,
    35,
    38,
    41,
    44,
    47
  ],
  "target": 29
}

Code

Pseudocode

function binarySearch(array, target):
  left = 0
  right = length(array) - 1

  while left <= right:
    mid = floor((left + right) / 2)

    if array[mid] == target:
      return mid          // Found!

    if array[mid] < target:
      left = mid + 1      // Search right half
    else:
      right = mid - 1     // Search left half

  return -1               // Not found

Python

def binary_search(array: list[int], target: int) -> int:
    left = 0
    right = len(array) - 1

    while left <= right:
        mid = (left + right) // 2

        if array[mid] == target:
            return mid

        if array[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

JavaScript

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

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

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

    if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

Key Concepts

Divide and Conquer

Binary search works by repeatedly dividing the search interval in half. If the target is less than the middle element, narrow to the left half. If greater, narrow to the right half.

Sorted Input Requirement

Binary search only works on sorted arrays. If the input is unsorted, the algorithm may miss the target entirely. Always verify the array is sorted before applying binary search.

Logarithmic Time Complexity

Each comparison eliminates half the remaining elements. For an array of n elements, this means at most ⌈log₂(n)⌉ comparisons. For 1 million elements, that’s at most 20 comparisons — compared to 1 million for linear search.

Integer Overflow in Mid Calculation

The classic formula mid = (left + right) / 2 can overflow for very large arrays. A safer alternative is mid = left + (right - left) / 2. In JavaScript with 64-bit floats this isn’t an issue for arrays up to 2⁵³, but it matters in languages with 32-bit integers like Java or C.

Common Pitfalls

• Off-by-one in boundaries: The most common binary search bug is using < instead of <= in the while condition, or forgetting the +1 / -1 when updating left and right. These cause the algorithm to miss elements or loop infinitely.
• Unsorted input: Binary search silently produces wrong results on unsorted arrays. It won’t crash — it’ll just return an incorrect answer. Always validate that input is sorted.
• Empty array: An empty array should return -1 immediately. The loop condition left <= right handles this correctly (0 <= -1 is false), but it’s worth testing explicitly.

Quiz

Q1: What is the maximum number of comparisons binary search needs for an array of 1024 elements?

• A) 10
• B) 11
• C) 32
• D) 1024

Show answer

Answer: B) 11

⌈log₂(1024)⌉ = 10, but we need one extra comparison for the final check, giving us at most 11 comparisons. Each comparison halves the space: 1024 → 512 → 256 → … → 1.

Q2: What happens if you use binary search on an unsorted array?

• A) It throws an error
• B) It always returns -1
• C) It may return a wrong index or miss the target
• D) It sorts the array first

Show answer

Answer: C) It may return a wrong index or miss the target

Binary search assumes the array is sorted. On an unsorted array, the comparisons are meaningless — the algorithm may eliminate the half that actually contains the target, returning an incorrect result with no warning.

Q3: What is the space complexity of binary search?

• A) O(1)
• B) O(log n)
• C) O(n)
• D) O(n log n)

Show answer

Answer: A) O(1)

Iterative binary search uses only a constant amount of extra memory (the left, right, and mid pointers), regardless of input size. The recursive version uses O(log n) stack space.

Further Reading

• Binary Search — Wikipedia (reference)
• Nearly All Binary Searches Are Broken (article)

Related Algorithms

• Bubble Sort
• QuickSort
• Merge Sort