AV
LibraryBinary Search

Binary Search

Easy

Binary Search is an efficient algorithm for finding an item from a sorted list by repeatedly dividing the search interval in half. It requires the input to be sorted.

Time Complexity

O(log n)

Space Complexity

O(1)

Category

Searching

Introduction to Binary Search

Binary Search is one of the most important search algorithms, providing O(log n) search time for sorted arrays. It's much faster than linear search and forms the foundation for many advanced data structures and algorithms.

How It Works

The algorithm works by repeatedly dividing the search space in half:

1. Start with the middle element of the sorted array

2. If it matches the target, return the index

3. If target is smaller, search the left half

4. If target is larger, search the right half

5. Repeat until found or search space is exhausted

Algorithm Complexity

**Time Complexity**: O(log n) - Each comparison eliminates half the remaining elements
**Space Complexity**: O(1) - Iterative version uses constant space

Prerequisites

**Input must be sorted**: This is absolutely essential
Works best on arrays or lists with random access

Best and Worst Cases

**Best Case**: O(1) - Element is at the center position
**Worst Case**: O(log n) - Element at the end or not present
**Average Case**: O(log n) - For random searches

Advantages

1. Very efficient - O(log n) time complexity

2. Space efficient - O(1) for iterative version

3. Predictable performance

4. Works on large datasets

5. Can be used for range queries

Disadvantages

1. Requires sorted input

2. Sorting has O(n log n) cost

3. Slower on small datasets than linear search

4. Not suitable for linked lists without random access

When to Use

**Large sorted datasets**: Excellent for searching databases
**Frequent searches**: When multiple searches make sorting worthwhile
**Real-time systems**: When O(log n) latency is required
**Phone books or directories**: Classic use case

Variations

1. **Recursive Binary Search**: Using recursion instead of iteration

2. **Exponential Search**: Find range first, then binary search

3. **Interpolation Search**: Estimates position based on value

4. **Lower/Upper Bound**: Finding first/last occurrence

Real-world Applications

Database index lookups
Phone directory searches
Version control systems
API endpoints
Memory management systems
Network routing tables

Key Takeaways

  • Works only on sorted arrays
  • Eliminates half elements per iteration
  • Logarithmic time complexity
  • Space efficient
  • Two-pointer approach
  • Fast for large datasets

Implementation

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Tags

searchingdivide-and-conquerefficientbeginner

Quick Stats

Difficulty:Easy
Type:Searching

Share