Binary Search Algorithm: Complete Guide with Code Examples

Binary search is one of the most important algorithms to master. It turns an O(n) linear scan into an O(log n) search — meaning you can search 1 billion sorted elements in roughly 30 comparisons. It's everywhere: database indexes, git bisect, Array.prototype.findIndex, and half the "medium" LeetCode problems once you see the pattern.

Quick reference

Time: O(log n)  ·  Space: O(1) iterative, O(log n) recursive call stack

How binary search works

Given a sorted array, binary search works by repeatedly halving the search space:

1. Look at the middle element.
2. If it equals the target → done.
3. If target < middle → search the left half.
4. If target > middle → search the right half.
5. Repeat until found or the search space is empty.

Array: [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
Target: 13

Step 1: lo=0, hi=9, mid=4  → arr[4]=9  < 13 → search right
Step 2: lo=5, hi=9, mid=7  → arr[7]=15 > 13 → search left
Step 3: lo=5, hi=6, mid=5  → arr[5]=11 < 13 → search right
Step 4: lo=6, hi=6, mid=6  → arr[6]=13 = 13 → FOUND at index 6

4 steps to find 13 in 10 elements. Linear search would need up to 10.

The classic template

There are many ways to write binary search; most bugs come from inconsistent boundary handling. Pick one template and stick with it.

Closed interval [lo, hi] — simplest mental model

// JavaScript
function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;          // closed: hi starts at last index

  while (lo <= hi) {                 // loop while space is non-empty
    const mid = lo + Math.floor((hi - lo) / 2);  // avoids integer overflow
    if (arr[mid] === target) return mid;
    if (arr[mid] < target)  lo = mid + 1;        // mid was too small, exclude it
    else                    hi = mid - 1;         // mid was too large, exclude it
  }

  return -1;                         // not found
}

console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 7));  // 3
console.log(binarySearch([1, 3, 5, 7, 9, 11, 13], 4));  // -1

# Python
def binary_search(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1

    return -1

# Python also has bisect built-in:
import bisect
arr = [1, 3, 5, 7, 9]
i = bisect.bisect_left(arr, 5)
if i < len(arr) and arr[i] == 5:
    print(i)  # 2

// Go
func binarySearch(arr []int, target int) int {
    lo, hi := 0, len(arr)-1

    for lo <= hi {
        mid := lo + (hi-lo)/2
        if arr[mid] == target {
            return mid
        } else if arr[mid] < target {
            lo = mid + 1
        } else {
            hi = mid - 1
        }
    }

    return -1
}

// Go stdlib: sort.SearchInts finds leftmost insertion point
// i := sort.SearchInts(arr, target)

<?php
function binarySearch(array $arr, int $target): int {
    $lo = 0;
    $hi = count($arr) - 1;

    while ($lo <= $hi) {
        $mid = $lo + intdiv($hi - $lo, 2);
        if ($arr[$mid] === $target) return $mid;
        if ($arr[$mid] < $target)   $lo = $mid + 1;
        else                        $hi = $mid - 1;
    }

    return -1;
}

Common pitfalls

1. Integer overflow in mid calculation

// WRONG — overflows for large indices in low-level languages
const mid = Math.floor((lo + hi) / 2);

// CORRECT — avoids overflow
const mid = lo + Math.floor((hi - lo) / 2);

JavaScript numbers are 64-bit floats so this rarely matters in practice, but it's a critical habit in Go, Java, and C++ where int is 32-bit.

2. Off-by-one: < vs <= in the while condition

// Closed interval [lo, hi]: use lo <= hi
// Loop exits when lo > hi (empty interval)
while (lo <= hi) { ... }

// Half-open interval [lo, hi): use lo < hi
// hi starts at arr.length, loop exits when lo === hi
while (lo < hi) { ... }

Mixing these causes either an infinite loop or a missed element at the boundary.

3. Infinite loop when lo = mid

// WRONG — if lo === hi === mid, lo never advances
while (lo < hi) {
  const mid = lo + Math.floor((hi - lo) / 2);
  if (condition(mid)) hi = mid;
  else lo = mid;       // ← infinite loop when lo + 1 === hi
}

// CORRECT — bias mid upward by adding 1
  const mid = lo + Math.floor((hi - lo + 1) / 2);
  // now lo = mid advances when hi - lo === 1

This matters in lower-bound variants where lo = mid is a valid move.

4. Searching an unsorted array

Binary search requires the array to be sorted (or to have a monotone property). Applying it to an unsorted array gives wrong answers silently.

Variations

Lower bound — first index ≥ target

Returns the leftmost position where target could be inserted to keep sorted order. Equivalent to Python's bisect_left.

// JavaScript — lower bound
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;   // hi = length (not length-1)

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else                   hi = mid;  // mid might be the answer, keep it
  }

  return lo;  // first index where arr[lo] >= target
}

const arr = [1, 3, 3, 3, 5, 7];
console.log(lowerBound(arr, 3));  // 1 — first 3
console.log(lowerBound(arr, 4));  // 4 — insertion point for 4

Upper bound — first index > target

Returns one past the last occurrence. Equivalent to Python's bisect_right.

// JavaScript — upper bound
function upperBound(arr, target) {
  let lo = 0, hi = arr.length;

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

  return lo;  // first index where arr[lo] > target
}

const arr = [1, 3, 3, 3, 5, 7];
console.log(upperBound(arr, 3));  // 4 — one past last 3
// count occurrences of 3:
console.log(upperBound(arr, 3) - lowerBound(arr, 3));  // 3

# Python — both built-in
import bisect

arr = [1, 3, 3, 3, 5, 7]
lo = bisect.bisect_left(arr, 3)   # 1
hi = bisect.bisect_right(arr, 3)  # 4
count = hi - lo                   # 3

Search in rotated sorted array

A sorted array rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2] from [0,1,2,4,5,6,7]). One half is always sorted.

// JavaScript — rotated array search
function searchRotated(arr, target) {
  let lo = 0, hi = arr.length - 1;

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

    // Determine which half is sorted
    if (arr[lo] <= arr[mid]) {
      // Left half is sorted
      if (arr[lo] <= target && target < arr[mid]) hi = mid - 1;
      else                                         lo = mid + 1;
    } else {
      // Right half is sorted
      if (arr[mid] < target && target <= arr[hi]) lo = mid + 1;
      else                                         hi = mid - 1;
    }
  }

  return -1;
}

console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 0));  // 4
console.log(searchRotated([4, 5, 6, 7, 0, 1, 2], 3));  // -1

# Python — same logic
def search_rotated(arr: list[int], target: int) -> int:
    lo, hi = 0, len(arr) - 1

    while lo <= hi:
        mid = lo + (hi - lo) // 2
        if arr[mid] == target:
            return mid

        if arr[lo] <= arr[mid]:          # left half sorted
            if arr[lo] <= target < arr[mid]:
                hi = mid - 1
            else:
                lo = mid + 1
        else:                            # right half sorted
            if arr[mid] < target <= arr[hi]:
                lo = mid + 1
            else:
                hi = mid - 1

    return -1

Binary search on the answer space

Many problems aren't "find a value in an array" but rather "find the minimum X such that some condition holds." The key insight: if condition(X) is false for small X and true for large X (monotone), you can binary search on X directly.

// Example: find minimum speed so a worker finishes all piles of bananas
// within h hours (Koko Eating Bananas — LeetCode 875)
function minEatingSpeed(piles, h) {
  function canFinish(speed) {
    let hours = 0;
    for (const p of piles) hours += Math.ceil(p / speed);
    return hours <= h;
  }

  let lo = 1, hi = Math.max(...piles);

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canFinish(mid)) hi = mid;  // mid works, try smaller
    else                lo = mid + 1;
  }

  return lo;
}

console.log(minEatingSpeed([3, 6, 7, 11], 8));   // 4
console.log(minEatingSpeed([30, 11, 23, 4, 20], 5));  // 30

Template for "find minimum X where condition is true":

# Python — answer space binary search template
def solve(lo: int, hi: int) -> int:
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if condition(mid):
            hi = mid        # mid is a valid answer, try smaller
        else:
            lo = mid + 1    # mid too small
    return lo               # minimum X where condition holds

Template for "find maximum X where condition is true":

def solve(lo: int, hi: int) -> int:
    while lo < hi:
        mid = lo + (hi - lo + 1) // 2  # bias up to avoid infinite loop
        if condition(mid):
            lo = mid        # mid works, try larger
        else:
            hi = mid - 1    # mid too large
    return lo               # maximum X where condition holds

Find peak element

A peak element is greater than its neighbours. The array may have multiple peaks; return any one. O(log n).

// JavaScript — find any peak
function findPeak(arr) {
  let lo = 0, hi = arr.length - 1;

  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] > arr[mid + 1]) hi = mid;  // peak on left side (or mid itself)
    else                          lo = mid + 1;
  }

  return lo;  // index of a peak
}

console.log(findPeak([1, 2, 3, 1]));   // 2 (value 3)
console.log(findPeak([1, 2, 1, 3, 5, 6, 4]));  // 5 (value 6)

Built-in binary search functions

// Go — sort.Search for answer space
package main

import (
    "fmt"
    "sort"
)

func main() {
    arr := []int{1, 3, 5, 7, 9, 11}

    // Lower bound: first index where arr[i] >= 5
    i := sort.SearchInts(arr, 5)
    fmt.Println(i, arr[i])  // 2, 5

    // Generic answer space: find smallest x in [lo, hi] where f(x) is true
    result := sort.Search(100, func(x int) bool {
        return x*x >= 50
    })
    fmt.Println(result)  // 8 (8² = 64 ≥ 50, 7² = 49 < 50)
}

Classic interview problems

Complexity analysis

How many comparisons for n elements?

Common mistakes

FAQ

Q: Binary search vs linear search — when does binary search win?

Binary search requires a sorted input. If sorting costs O(n log n) and you only search once, linear search at O(n) is faster. Binary search wins when you search many times (amortized cost of sorting is spread over all searches), or when the data is already sorted.

Q: Can binary search work on strings?

Yes, on sorted arrays of strings (lexicographic order). The same template applies; comparisons use string < / >.

Q: What is the difference between lower bound and floor?

• Lower bound (bisect_left): first index where arr[i] >= target. If target is missing, returns the insertion point.
• Floor: largest value ≤ target. Use lowerBound(target) - 1 then check if that index is ≥ 0 and arr[i] <= target.

Q: How do I binary search on a sorted 2D matrix?

Treat the matrix as a flattened 1D array of length rows × cols. Map index i to (row, col) as (i / cols, i % cols).

function searchMatrix(matrix, target) {
  const rows = matrix.length, cols = matrix[0].length;
  let lo = 0, hi = rows * cols - 1;

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

  return false;
}

Q: Why does git bisect use binary search?

git bisect finds the first "bad" commit in history. If commits are ordered (good → good → ... → bad → bad → ...), the boundary is monotone. Binary search finds it in O(log n) commits tested instead of O(n).

Q: Is binary search the same as a binary search tree (BST)?

No. Binary search is an algorithm on sorted arrays. A binary search tree (BST) is a data structure where each node's left subtree has smaller values and right subtree has larger values. BST traversal exploits the same O(log n) property but on a tree rather than an array. A balanced BST (AVL, Red-Black) guarantees O(log n); an unbalanced BST degrades to O(n).