Binary Search

Finds the index of a target in a sorted array

Problem Overview

🔍 The Foundation of Efficient Searching
Binary search is the gold standard for searching sorted arrays, cutting the search space in half with each comparison. This divide-and-conquer masterpiece achieves O(log n) performance!

🧠 How Binary Search Works:

Start with the middle element of the sorted array
Compare target with middle: equal (found!), less (search left half), greater (search right half)
Repeat on the selected half until found or exhausted
Return index if found, -1 if not found
Two Implementation Approaches:
Iterative Method: Uses loops with O(1) space complexity (optimal)
Recursive Method: Clean recursive calls with O(log n) space overhead

🎓 Interview & Learning Value:

Essential algorithm for technical interviews
Demonstrates divide-and-conquer strategy
Foundation for more complex search algorithms
Real-world applications in databases and file systems
Real-World Applications:
Database indexing and query optimization
Git bisect for finding buggy commits
Memory allocation in operating systems
Search suggestions and autocomplete systems

Concepts

divide-and-conquerlogarithmic search

Complexity Analysis

Time:O(log n)

Space:O(1) for iterative, O(log n) for recursive

Solutions

binarySearch

Time: O(log n) | Space: O(1)

export function binarySearch(arr: number[], target: number): number {
  if (!Array.isArray(arr) || !arr.every(Number.isFinite)) throw new Error("Input must be a sorted array of numbers");
  if (typeof target !== 'number' || !Number.isFinite(target)) throw new Error("Target must be a finite number");
  let low = 0;
  let high = arr.length - 1;
  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);
    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Examples & Test Cases

#1Middle

Input:

Output:2

#2Not found

Input:

Output:-1

#3Empty

Input:

[
  [],
  5
]

Output:-1

#4Single found

Input:

[
  [
    1
  ],
  1
]

Output:0

#5Single not found

Input:

[
  [
    1
  ],
  2
]

Output:-1

#6Duplicates

Input:

Output:1