FAANGPrep Sprint

Binary Search

Efficiently find an element in a sorted array by repeatedly dividing the search interval in half.

Easy

15 min

What is Binary Search?

Binary Search is a foundational algorithm for finding a target value within a sorted array. It works by repeatedly comparing the target to the middle element of the array.

The Motivation: Dictionary Search

Imagine finding a word in a dictionary. You don't read every word from the start (Linear Search). Instead, you open the book to the middle. If the target word is alphabetically after the middle, you discard the first half and search the second half. You repeat this until you find the word.

Attempt 1: Linear Search (Brute Force)

The simplest way is to check every element from left to right.

function search(nums: number[], target: number): number {
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === target) return i;
    }
    return -1;
}

Why it fails

Time Complexity: O(n). If the array has 1 billion elements, you might make 1 billion comparisons.
Inefficient: It ignores the fact that the array is sorted.

The Intuition: Divide and Conquer

Since the array is sorted, we can rule out half of the elements in one step.

Pick the middle element.
If middle === target, we are done.
If middle < target, the target must be in the right half (every element to its left is smaller).
If middle > target, the target must be in the left half.
Repeat on the smaller subarray.

Interactive Walkthrough

TARGET 9

READY

-1

Left

Mid

—

Right

Result

—

Search the whole array for 9: left = 0, right = 5

mid = 0 + (5 - 0) / 2 = 2, and nums[2] = 3

Array

Target

Legend & Complexity

nums[mid], the element being compared with the target

The target, once found

Outside [left, right]: ruled out (struck through)

Time

O(log n)

Extra space

O(1)

Step through the algorithm to see how the search range shrinks.

Dry Run Table

Dry Run: Target = 9

Array: [-1, 0, 3, 5, 9, 12]

Step	Low	High	Mid	Value	Comparison	Action
1	0	5	2	3	3 < 9	Target is right. Low = 3 (Mid+1)
2	3	5	4	9	9 == 9	Found!

The Solution Template

Standard Binary Search implementation.

Binary Search Code

1/**
2 * @param {number[]} nums
3 * @param {number} target
4 * @return {number}
5 */
6var search = function(nums, target) {
7    let left = 0;
8    let right = nums.length - 1;
9
10    while (left <= right) {
11        // Prevent potential integer overflow compared to (left + right) / 2
12        let mid = Math.floor(left + (right - left) / 2);
13
14        if (nums[mid] === target) {
15            return mid;
16        } else if (nums[mid] < target) {
17            left = mid + 1;
18        } else {
19            right = mid - 1;
20        }
21    }
22
23    return -1;
24};

Edge Cases

Empty array: Should return -1 immediately.
Target not found: Loop completes, return -1.
Single element: Start/Mid/End are all same index.
Integer Overflow: Using mid = (left + right) / 2 can overflow in languages like C++/Java if left+right > 2^31. Use mid = left + (right-left)/2.

Summary

Binary Search reduces the search space by half at every step, achieving O(log n) efficiency. Standard on sorted arrays.

Previous Problem

Longest Valid Parentheses

Next Problem

Koko Eating Bananas