Kata: Binary Search

Table of contents

Problem Statement

Part 1: Classic Binary Search

Given a sorted array and a target value, return the index of the target or -1 if not found. Implement both iterative and recursive versions.

Part 2: Search Insert Position

Given a sorted array and a target, return the index where the target is found, or the index where it would be inserted to keep the array sorted.

Concepts

Binary search eliminates half of the remaining elements at each step, achieving O(log n) time. It requires a sorted input.

The key insight: compare the target with the middle element. If the target is smaller, search the left half; if larger, search the right half.

Python: The bisect module provides production-ready binary search. See Python Core Concepts.

Boilerplate

TypeScript

// binary-search.ts
function binarySearch(nums: number[], target: number): number {
  // TODO: iterative
  return -1;
}

function binarySearchRecursive(
  nums: number[],
  target: number,
  left: number = 0,
  right: number = nums.length - 1
): number {
  // TODO: recursive
  return -1;
}

function searchInsert(nums: number[], target: number): number {
  // TODO
  return 0;
}

Hints

Solution

TypeScript

function binarySearch(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

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

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

  return -1;
}

function binarySearchRecursive(
  nums: number[],
  target: number,
  left: number = 0,
  right: number = nums.length - 1
): number {
  if (left > right) return -1;

  const mid = left + Math.floor((right - left) / 2);

  if (nums[mid] === target) return mid;
  if (nums[mid] < target) {
    return binarySearchRecursive(nums, target, mid + 1, right);
  }
  return binarySearchRecursive(nums, target, left, mid - 1);
}

function searchInsert(nums: number[], target: number): number {
  let left = 0;
  let right = nums.length - 1;

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

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

  return left;
}

Python

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

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

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1

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

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

        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return left

# Production alternative: use bisect
from bisect import bisect_left

def search_insert_bisect(nums: list[int], target: int) -> int:
    return bisect_left(nums, target)

Complexity Analysis

Cross-Language Notes

Python: The bisect module provides bisect_left, bisect_right, and insort for binary search and sorted insertion. It’s implemented in C for performance. Always prefer bisect in production Python code.

PHP: PHP provides array_search() but it’s linear. For binary search on sorted arrays, you need a manual implementation or a library.

Java: Arrays.binarySearch() and Collections.binarySearch() provide built-in implementations.

Common bug: Off-by-one errors are the most frequent binary search bug. Test edge cases: empty array, single element, target at boundaries, target not present.