Algorithms from zero

Binary search

Crux Binary search finds a value in a sorted array in O(log n) by repeatedly halving the search range. The precondition: the array must be sorted. The idea: keep bounds [lo, hi], check the middle element, discard half the range, repeat.

◷ 18 min

You have a sorted array and need to find a value. Linear search walks the array one element at a time: O(n). For small arrays, this is fine. For large arrays—millions or billions of elements—linear search is too slow. Here is the payoff of sorting: once sorted, you can use binary search. The idea is simple: check the middle element. If it is your target, done. If your target is smaller, discard the right half and search the left half. If your target is larger, discard the left half and search the right half. Each step halves the search space. After ~20 steps, a million-element array is narrowed to a single element. That is O(log n)—the logarithm measures how many times you can halve n before nothing is left.

Goal

After this lesson you understand binary search: the precondition (the array must be sorted), the algorithm (maintain bounds, check the middle, discard half, repeat), why it is O(log n) (you halve the search space roughly log n times), the implementation pitfalls (the loop condition lo <= hi, computing mid without overflow, and getting the boundary updates correct to avoid infinite loops), and what binary search returns (the index if found, or a “not found” signal if not).

The idea

The precondition: the array must be sorted

Binary search only works on sorted arrays. If the array is unsorted, binary search will miss values and give wrong answers. This is why sorting is preprocessing—once you pay O(n log n) to sort, you unlock O(log n) binary search.

Example: Array [1, 3, 5, 7, 9, 11]. This is sorted. Binary search will work correctly.

Array [3, 1, 7, 5, 11, 9]. This is unsorted. Binary search will fail.

The idea: keep bounds and halve

Binary search maintains two bounds: lo (the lowest index still in play) and hi (the highest index still in play). The search range is [lo, hi]—all elements from index lo to index hi, inclusive.

At each step:

Compute the middle index: mid = Math.floor((lo + hi) / 2).
Check if arr[mid] equals the target. If yes, return mid.
If arr[mid] is less than the target, the target is in the right half. Discard the left half: set lo = mid + 1.
If arr[mid] is greater than the target, the target is in the left half. Discard the right half: set hi = mid - 1.
Repeat until lo > hi (the search range is empty; target not found).

Why O(log n)?

At each step, the search range shrinks by half. How many times can you halve n?

From the math track Logarithms

Starting with n elements:

After step 1: ~n/2 elements left.
After step 2: ~n/4 elements left.
After step 3: ~n/8 elements left.
…
After step log₂(n): ~1 element left (or 0, meaning not found).

So the maximum number of iterations is log₂(n). For n = 1,000,000, that is log₂(1,000,000) ≈ 20 steps. Compare that to linear search: 500,000 steps on average.

The loop condition: lo <= hi

The loop continues as long as the search range is non-empty: lo <= hi. When lo > hi, the range is empty, and the target is not in the array.

Pitfall 1: The loop condition

A common mistake is using lo < hi instead of lo <= hi. If you do, you will miss the case where lo == hi (a single element left). Use lo <= hi to check that element.

Pitfall 2: Computing mid

Computing mid = (lo + hi) / 2 can overflow in languages with fixed-size integers (Java, C++). If lo and hi are very large, lo + hi might exceed the maximum integer value.

Safe formula: mid = lo + Math.floor((hi - lo) / 2). Or equivalently: mid = lo + ((hi - lo) >> 1) (bit shift right by 1 is integer division by 2).

JavaScript does not have this overflow issue, but it is good practice.

Pitfall 3: Boundary updates

After deciding to discard a half, you must update the boundary correctly:

If the target is in the right half, set lo = mid + 1 (not lo = mid). If you set lo = mid and arr[mid] is not the target, you will loop forever, always checking the same mid.
If the target is in the left half, set hi = mid - 1 (not hi = mid). Same reason.

What does binary search return?

If the target is found, return its index. If not found, return -1 (or null, or throw an error—depending on your design).

The code

Let us code binary search from scratch.

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

  while (lo <= hi) {
    // Compute mid safely
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === target) {
      return mid;  // Found!
    } else if (arr[mid] < target) {
      // Target is in the right half
      lo = mid + 1;
    } else {
      // Target is in the left half
      hi = mid - 1;
    }
  }

  // Loop exited: lo > hi. Target not found.
  return -1;
}

Key points:

lo and hi are inclusive bounds (both endpoints are part of the search range).
mid = lo + Math.floor((hi - lo) / 2) avoids overflow and rounds down.
lo = mid + 1 and hi = mid - 1 ensure the range always shrinks (no infinite loops).
The loop continues while lo <= hi.

Let us test it:

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

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

// Test 1: target exists
const arr1 = [1, 3, 5, 7, 9, 11, 13];
console.log("Array:", arr1);
console.log("Search for 7:", binarySearch(arr1, 7), "(expected 3)");
console.log("Search for 1:", binarySearch(arr1, 1), "(expected 0)");
console.log("Search for 13:", binarySearch(arr1, 13), "(expected 6)");

// Test 2: target does not exist
console.log("Search for 6:", binarySearch(arr1, 6), "(expected -1)");
console.log("Search for 0:", binarySearch(arr1, 0), "(expected -1)");
console.log("Search for 20:", binarySearch(arr1, 20), "(expected -1)");

// Test 3: edge case — single element
const arr2 = [42];
console.log("Single element [42], search for 42:", binarySearch(arr2, 42), "(expected 0)");
console.log("Single element [42], search for 10:", binarySearch(arr2, 10), "(expected -1)");

// Test 4: larger array
const arr3 = Array.from({length: 100}, (_, i) => i * 2);  // [0, 2, 4, ..., 198]
console.log("Large array (100 elements), search for 50:", binarySearch(arr3, 50), "(expected 25)");
console.log("Large array, search for 51:", binarySearch(arr3, 51), "(expected -1)");

Output

Step-by-step trace

Let us trace binary search on array [1, 3, 5, 7, 9, 11], searching for target = 7.


      1
      while (lo <= hi) {
    

      2
        const mid = lo + Math.floor((hi - lo) / 2);
    

      3
        if (arr[mid] === target) return mid;
    

      4
        else if (arr[mid] < target) lo = mid + 1;
    

      5
        else hi = mid - 1;
    

      6
      }

Breakdown:

Step 1: Search range [0, 5]. Check index 2 (value 5). Too small; search right half [3, 5].
Step 2: Search range [3, 5]. Check index 4 (value 9). Too big; search left half [3, 3].
Step 3: Search range [3, 3]. Check index 3 (value 7). Found! Return 3.

Total steps: 3. For an unsorted array of 6 elements, linear search would scan all 6. Binary search scanned 3.

Complexity

Aspect	Value
Time (best case)	O(1) — target is the middle element on the first check
Time (average case)	O(log n)
Time (worst case)	O(log n) — target is at the edge, or not found
Space	O(1) — only two pointers and mid index

Why O(log n)?

Each iteration halves the search range. The range starts with n elements and shrinks: n → n/2 → n/4 → … → 1. The number of halvings is log₂(n).

For different array sizes:

n	log₂(n)
100	~7 steps
1,000	~10 steps
1,000,000	~20 steps
1,000,000,000	~30 steps

Linear search on 1 billion elements: 500 million comparisons. Binary search: 30 comparisons. The speedup is astronomical.

Precondition: the array must be sorted

If the array is unsorted, binary search will give wrong answers. The sort costs O(n log n) once. Afterward, every search is O(log n). This amortizes the cost of sorting over many searches.

If you search only once, O(n log n) sort + O(log n) search = O(n log n) total. Linear search is O(n). For a single search, linear is better. But for multiple searches, binary search wins.

Space: O(1)

Binary search uses only a constant amount of extra memory: two pointers (lo, hi) and one index (mid). Recursive implementations add O(log n) on the call stack (the depth of recursion is log n), but the iterative version (shown here) is O(1).

Practice 0 / 5

Why does binary search require a sorted array?

How many comparisons does binary search need in the worst case to search an array of 1,000 elements?

What does binary search return if the target is not in the array?

Why is `mid = lo + Math.floor((hi - lo) / 2)` safer than `mid = (lo + hi) / 2`?

When you find that arr[mid] < target, why do you set `lo = mid + 1` instead of `lo = mid`?

Common mistake

The off-by-one / infinite loop bug. The most common mistake is setting lo = mid or hi = mid instead of lo = mid + 1 or hi = mid - 1. If arr[mid] is not the target, and you set lo = mid, the loop will re-check arr[mid] forever, creating an infinite loop. Always use mid + 1 and mid - 1 to shrink the range.

lesson.inset.edge-case

Edge cases. Test your binary search on small arrays: single element, two elements, empty array (if applicable). Test when the target is the first element, the last element, and missing entirely. These edge cases often expose loop condition bugs.

Check yourself

Quiz

You have a sorted array of 10 million elements and must find if a target exists. Is binary search faster than linear search? By how much?

Recap

Binary search finds a value in a sorted array by repeatedly halving the search range.

Precondition: The array must be sorted.

The algorithm: Maintain bounds lo and hi. Check the middle element arr[mid]. If it is the target, return its index. Otherwise, discard half the range (left or right), and repeat. When lo > hi, the range is empty; return “not found.”

Time complexity: O(log n) because you halve the search space roughly log n times. For 1 billion elements, ~30 steps. Much faster than linear search (500 million steps).

Space complexity: O(1) for the iterative version (two pointers and an index).

Pitfalls:

Use lo <= hi to include the case lo == hi (the last single element).
Use lo + Math.floor((hi - lo) / 2) to avoid overflow.
Use lo = mid + 1 and hi = mid - 1 to ensure the range shrinks each iteration (avoid infinite loops).

When to use it: After sorting, for fast repeated searches on large data.

Why learn it? Binary search is one of the most important algorithms in computer science. It teaches you how to exploit sorted order for speed, and shows that O(log n) is achievable in practice.

Continue the climb ↑Binary search on the answer