Skip to main content
Binary search is an efficient search algorithm that finds the position of a target value within a sorted array by repeatedly dividing the search interval in half.

​
Algorithm overview

Binary search works by comparing the target value to the middle element of the array. If they match, the position is returned. If the target is less than the middle element, the search continues in the lower half. If greater, it continues in the upper half. This process repeats until the value is found or the search space is empty.

​
Key characteristics

  • Requires a sorted array
  • Uses divide-and-conquer strategy
  • Much faster than linear search for large datasets
  • Available in both iterative and recursive implementations
Binary search only works correctly on sorted arrays. Using it on unsorted data will produce incorrect results.

​
Implementation

The repository includes both iterative and recursive implementations.
binary-search.ts
export function binarySearch<T = number>(list: T[], value: T) {
  let start = 0;
  let end = list.length - 1;

  while (end >= start) {
    const middle = start + Math.floor((end - start) / 2);

    if (list[middle] === value) {
      return middle;
    }

    if (value > list[middle]) {
      start = middle + 1;
    }

    if (value < list[middle]) {
      end = middle - 1;
    }
  }

  return -1;
}
binary-search.ts
export function recursiveBinarySearch<T = number>(
  list: T[],
  value: T,
  start: number,
  end: number
): number {
  if (start >= end) {
    return -1;
  }

  const middle = Math.floor((end + start) / 2);

  // Base case
  if (list[middle] === value) {
    return middle;
  }

  return list[middle] < value
    ? recursiveBinarySearch(list, value, middle + 1, end)
    : recursiveBinarySearch(list, value, start, middle - 1);
}

​
Function signatures

function binarySearch<T = number>(list: T[], value: T): number

​
Complexity analysis

  • Best case: O(1) - Element is at the middle position
  • Average case: O(log n) - Element requires multiple divisions
  • Worst case: O(log n) - Element is at an end or not present
The algorithm divides the search space in half with each iteration, resulting in logarithmic time complexity. This makes it extremely efficient for large datasets.For example:
  • Array of 1,000 elements: ~10 comparisons maximum
  • Array of 1,000,000 elements: ~20 comparisons maximum
  • Iterative: O(1) - Constant space
  • Recursive: O(log n) - Call stack depth
The iterative version uses only a few variables. The recursive version uses stack space proportional to the number of recursive calls.

​
Usage examples

​
Basic usage (iterative)

import { binarySearch } from './binary-search';

// Array must be sorted
const numbers = [1, 2, 3, 4, 5, 6];

// Find an element that exists
const index = binarySearch(numbers, 5);
console.log(index); // Output: 4

// Search for non-existent element
const notFound = binarySearch(numbers, 7);
console.log(notFound); // Output: -1

​
Recursive usage

import { recursiveBinarySearch } from './binary-search';

const numbers = [1, 2, 3, 4, 5, 6];

const index = recursiveBinarySearch(
  numbers,
  5,
  0,
  numbers.length - 1
);
console.log(index); // Output: 4

​
Searching in sorted strings

const names = ['Alice', 'Bob', 'Charlie', 'David', 'Eve'];

const result = binarySearch(names, 'Charlie');
console.log(result); // Output: 2

​
Finding insertion point

// Modified binary search to find insertion point
function findInsertionPoint<T>(list: T[], value: T): number {
  let start = 0;
  let end = list.length - 1;
  
  while (start <= end) {
    const middle = start + Math.floor((end - start) / 2);
    
    if (list[middle] === value) {
      return middle;
    }
    
    if (value > list[middle]) {
      start = middle + 1;
    } else {
      end = middle - 1;
    }
  }
  
  return start; // Insertion point
}

const numbers = [1, 3, 5, 7, 9];
const insertPos = findInsertionPoint(numbers, 6);
console.log(insertPos); // Output: 3

​
How it works

Let’s visualize searching for the value 5 in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
1

Initial state

Start: 0, End: 8, Middle: 4Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]Compare 5 with middle element (5): Match found!Return index 4
Now searching for 7:
1

First iteration

Start: 0, End: 8, Middle: 4Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]Compare 7 with 5: 7 > 5, search right half
2

Second iteration

Start: 5, End: 8, Middle: 6Array: [1, 2, 3, 4, 5, 6, 7, 8, 9]Compare 7 with 7: Match found!Return index 6

Good for

  • Large sorted datasets
  • Multiple searches on same data
  • Performance-critical applications
  • When O(log n) matters

Avoid when

  • Unsorted data (sort first or use linear search)
  • Very small arrays (< 10 elements)
  • Linked lists (need random access)
  • Frequent insertions/deletions

​
Iterative vs recursive

​
Advantages

  • Constant O(1) space complexity
  • No risk of stack overflow
  • Slightly faster in practice
  • Preferred for production code

​
Use when

  • Working with large datasets
  • Memory efficiency is important
  • In resource-constrained environments

​
Common pitfalls

Integer overflow: When calculating middle index, (start + end) / 2 can overflow for very large arrays. Use start + Math.floor((end - start) / 2) instead.
Boundary conditions: Pay careful attention to <= vs < in loop conditions and middle + 1 vs middle - 1 when updating bounds.

​
Performance comparison

Array sizeLinear searchBinary search
1010 ops4 ops
100100 ops7 ops
1,0001,000 ops10 ops
10,00010,000 ops14 ops
1,000,0001,000,000 ops20 ops

Linear search

Simple sequential search for unsorted arrays

Breadth-first search

Level-by-level graph traversal algorithm

Build docs developers (and LLMs) love

Get started for freeTalk to us