Learn Binary Search – Algorithm Guide

01

Deep Dive: Overview

Binary Search is a highly efficient search algorithm that follows the Divide and Conquer paradigm. Instead of scanning through a collection element by element (which is how a Linear Search operates in O(N) time), Binary Search drastically reduces the search space by cutting it in half after every single comparison.

Why is it so powerful?

To understand its power, consider searching through an array of one million items. A linear search might take up to one million checks in the worst-case scenario. Binary search guarantees a result in a maximum of just 20 steps.

02

Prerequisites & Rules

Before implementing Binary Search, the data structure must meet two strict requirements:

1. Random Access

The underlying data structure must allow for direct index access in O(1) time. This is why binary search is perfect for Arrays, but highly inefficient for Linked Lists.

⚠️

The Golden Rule — Monotonicity: The array must be sorted (either strictly increasing or strictly decreasing). Sorting an array takes O(N log N) time, so sorting just to perform a single binary search is counterproductive. It is best used when searching an array multiple times.

03

Algorithm & Visualizer

The logic mirrors looking up a word in a dictionary. You open the book to the middle. If your target word precedes the page you are on, you know with absolute certainty it is in the left half. You ignore the right half entirely and repeat the process.

JavaScript

function binarySearch(arr, target) {
  let low = 0;
  let high = arr.length - 1;

  while (low <= high) {
    let mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) low = mid + 1;
    else high = mid - 1;
  }
  return -1;
}

Interactive Visualizer

Let's simulate the algorithm. We are searching for the target number 88.

Awaiting execution...

Low: 0 Mid: - High: 9

04

Mathematical Complexity

Time Complexity

Best Case: O(1) - The target is exactly at the middle index on the first calculation.
Worst Case: O(log N) - The target is at the very ends of the array, or doesn't exist.
Average Case: O(log N)

Space Complexity

Iterative: O(1) - Only requires storing three pointer variables (low, high, mid).
Recursive: O(log N) - Requires memory overhead for the call stack during recursive halving.

05

Practice Exercises

Binary search variations are heavily tested in technical interviews. Master these patterns to build your intuition:

Basic Implementation (LeetCode 704)

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums.

Solve on LeetCode

Search Insert Position (LeetCode 35)

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

Solve on LeetCode

Find First/Last Position (LeetCode 34)

Find the starting and ending position of a given target value in a sorted array.

Solve on LeetCode

Search in Rotated Sorted Array (LeetCode 33)

Search for a target value in a sorted array that has been rotated at an unknown pivot.

Solve on LeetCode

Algo Infinity Verse

Master the Binary Search Algorithm Logarithmic Time Searching in O(log n)