Binary Search

Back to DSA & Algorithms/00 - Roadmap Overview

What is Binary Search?

Binary search finds a target in a sorted collection by repeatedly cutting the search space in half. Instead of checking every element (O(n)), you check the middle, then decide which half to keep (O(log n)).

Why O(log n)?

n = 1,000,000 elements
Step 1: 1,000,000 → 500,000
Step 2: 500,000   → 250,000
Step 3: 250,000   → 125,000
...
Step 20: 1 element → FOUND

Only 20 steps to search 1 million elements!
log₂(1,000,000) ≈ 20

The Prerequisite

Binary search requires monotonicity: a property that is False for all elements before some point, and True for all elements after (or vice versa). Sorted arrays have this naturally, but it applies more broadly.

Sorted array:    [1, 3, 5, 7, 9, 11]
"Is it >= 7?":    F  F  F  T  T   T
                        ↑ boundary

The Three Templates You Must Know

There are multiple valid binary search templates. The differences are subtle but critical. Know when to use each one.

Template 1: Find Exact Match (`lo <= hi`)

java
public int binarySearch(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;

    while (lo <= hi) {                          // Note: <=
        int mid = lo + (hi - lo) / 2;           // Prevents overflow
        if (nums[mid] == target) {
            return mid;                         // Found it!
        } else if (nums[mid] < target) {
            lo = mid + 1;                       // Target is in right half
        } else {
            hi = mid - 1;                       // Target is in left half
        }
    }

    return -1; // Not found
}

// Use when: You want to find the exact position of a specific value
// Loop ends when: lo > hi (search space is empty)

Template 2: Find Left Boundary (`lo < hi`)

java
public int bisectLeft(int[] nums, int target) {
    int lo = 0, hi = nums.length;               // Note: hi = nums.length, not length-1

    while (lo < hi) {                            // Note: < (not <=)
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) {
            lo = mid + 1;                        // mid is too small
        } else {
            hi = mid;                            // mid could be the answer
        }
    }

    return lo; // Insertion point / first position >= target
}

// Use when: You want the FIRST position where condition is true
// Loop ends when: lo == hi (single candidate)

Template 3: Find Right Boundary

java
public int bisectRight(int[] nums, int target) {
    int lo = 0, hi = nums.length;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) {               // Note: <= (not <)
            lo = mid + 1;                        // mid is not past the target yet
        } else {
            hi = mid;
        }
    }

    return lo; // First position > target (so lo-1 is last position <= target)
}

The Critical Differences

	Template 1	Template 2	Template 3
Loop condition	`lo <= hi`	`lo < hi`	`lo < hi`
Returns	Exact match or -1	First `>= target`	First `> target`
`hi` initial	`length-1`	`length`	`length`
Shrink right	`hi = mid - 1`	`hi = mid`	`hi = mid`
When `==` found	Return immediately	Keep searching left	Keep searching right

Why `lo + (hi - lo) / 2` Instead of `(lo + hi) / 2`?

java
// In Java (and C++), integers have a fixed size (32-bit):
int lo = 2_000_000_000;
int hi = 2_000_000_000;
(lo + hi) / 2;           // OVERFLOW! 4 billion > Integer.MAX_VALUE (2.1 billion)
lo + (hi - lo) / 2;      // Safe: 2B + 0 = 2B

// Java int division already truncates toward zero, which floors for positive values.
// Always use the safe version — interviewers notice.

Pattern 1: Classic Binary Search

Find exact value in sorted array.

java
// Input: nums = [-1, 0, 3, 5, 9, 12], target = 9
// Output: 4

public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return -1;
}

Search in 2D Matrix

Treat the 2D matrix as a 1D sorted array.

java
// Matrix where each row is sorted and first element of each row > last of previous
public boolean searchMatrix(int[][] matrix, int target) {
    int rows = matrix.length, cols = matrix[0].length;
    int lo = 0, hi = rows * cols - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        // Convert 1D index to 2D coordinates
        int val = matrix[mid / cols][mid % cols];
        if (val == target) {
            return true;
        } else if (val < target) {
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }

    return false;
}

// Key formula:
// row = index / num_columns
// col = index % num_columns

Problems

704. Binary Search - Easy
74. Search a 2D Matrix - Medium

Pattern 2: Finding Boundaries

What it is

Instead of finding an exact value, find the first or last position where a condition is true.

The Mental Model

Imagine a row of light switches. All the ones on the left are OFF, all the ones on the right are ON. You want to find where the transition happens. You check the middle switch:

If OFF → transition is to the right
If ON → transition might be here or to the left

Step-by-Step: First and Last Position

java
// Input: nums = [5,7,7,8,8,10], target = 8
// Output: [3, 4] (first 8 at index 3, last 8 at index 4)

public int[] searchRange(int[] nums, int target) {
    int left = findLeft(nums, target);
    int right = findRight(nums, target);

    // Check if target actually exists
    if (left <= right && left < nums.length && nums[left] == target) {
        return new int[]{left, right};
    }
    return new int[]{-1, -1};
}

private int findLeft(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < target) {    // Too small, go right
            lo = mid + 1;
        } else {                     // >= target, could be answer
            hi = mid;
        }
    }
    return lo;
}

private int findRight(int[] nums, int target) {
    int lo = 0, hi = nums.length;
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] <= target) {   // <= target, go right
            lo = mid + 1;
        } else {                     // > target, could be answer
            hi = mid;
        }
    }
    return lo - 1;                   // -1 because lo is PAST the last target
}

// Walkthrough for findLeft with target=8:
// nums = [5, 7, 7, 8, 8, 10]
// lo=0, hi=6
// mid=3: nums[3]=8 >= 8 → hi=3
// lo=0, hi=3, mid=1: nums[1]=7 < 8 → lo=2
// lo=2, hi=3, mid=2: nums[2]=7 < 8 → lo=3
// lo=3 == hi=3 → return 3 ✓

Problems

34. Find First and Last Position - Medium
35. Search Insert Position - Easy
278. First Bad Version - Easy

Pattern 3: Rotated Sorted Array

What it is

A sorted array has been rotated at some unknown pivot. One half is always sorted.

Original: [0, 1, 2, 4, 5, 6, 7]
Rotated:  [4, 5, 6, 7, 0, 1, 2]
                    ↑ pivot
Left half [4,5,6,7] is sorted
Right half [0,1,2] is sorted

The Key Insight

At any mid, at least one half (left or right) is guaranteed to be sorted. Check which half is sorted, then check if the target falls in that sorted half.

java
public int search(int[] nums, int target) {
    int lo = 0, hi = nums.length - 1;

    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        // Which half is sorted?
        if (nums[lo] <= nums[mid]) {
            // LEFT half is sorted [lo...mid]
            if (nums[lo] <= target && target < nums[mid]) {
                hi = mid - 1;   // Target is in the sorted left half
            } else {
                lo = mid + 1;   // Target is in the unsorted right half
            }
        } else {
            // RIGHT half is sorted [mid...hi]
            if (nums[mid] < target && target <= nums[hi]) {
                lo = mid + 1;   // Target is in the sorted right half
            } else {
                hi = mid - 1;   // Target is in the unsorted left half
            }
        }
    }

    return -1;
}

// Walkthrough: nums = [4,5,6,7,0,1,2], target = 0
// lo=0, hi=6, mid=3: nums[3]=7 ≠ 0
//   nums[0]=4 <= nums[3]=7 → left half [4,5,6,7] sorted
//   Is 4 <= 0 < 7? No → target not in sorted half → lo=4
// lo=4, hi=6, mid=5: nums[5]=1 ≠ 0
//   nums[4]=0 <= nums[5]=1 → left half [0,1] sorted
//   Is 0 <= 0 < 1? Yes → hi=4
// lo=4, hi=4, mid=4: nums[4]=0 = 0 → Found! Return 4

Find Minimum in Rotated Array

java
public int findMin(int[] nums) {
    int lo = 0, hi = nums.length - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi]) {
            lo = mid + 1;     // Minimum is in the right half
        } else {
            hi = mid;         // Minimum is here or to the left
        }
    }

    return nums[lo];
}

// The minimum is the only element where nums[i] < nums[i-1]
// (or the first element if not rotated)

Problems

33. Search in Rotated Sorted Array - Medium
153. Find Minimum in Rotated Sorted Array - Medium
81. Search in Rotated Sorted Array II - Medium (with duplicates)

Pattern 4: Binary Search on Answer Space

What it is

The array isn't what you're searching — you're searching the answer itself. You binary search on a range of possible answers, checking if each one is feasible.

When to use it

"Find the minimum value such that some condition is satisfied"
"Find the maximum value such that some condition is satisfied"
The condition is monotonic: once it becomes True, it stays True (or vice versa)

The Mental Model

You're Goldilocks testing porridge temperatures. You know there's a range of temperatures from 0°C to 100°C. You want the minimum temperature that's "just right." Instead of testing 1°C, 2°C, 3°C... you test 50°C first. Too cold? Try 75°C. Too hot? Try 62°C. This is binary search on the answer.

Step-by-Step: Koko Eating Bananas

java
// Problem: Koko has piles of bananas. She eats K bananas/hour.
// Find minimum K to finish all piles in H hours.
//
// Input: piles = [3, 6, 7, 11], h = 8
// Answer: K = 4
//   At K=4: ceil(3/4) + ceil(6/4) + ceil(7/4) + ceil(11/4) = 1+2+2+3 = 8 hours ✓

public int minEatingSpeed(int[] piles, int h) {
    // Answer range: [1, max(piles)]
    // K=1: eats 1/hour (slowest possible)
    // K=max(piles): finishes any pile in 1 hour (fastest needed)
    int lo = 1;
    int hi = 0;
    for (int pile : piles) {
        hi = Math.max(hi, pile);
    }

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;

        // Can Koko finish in H hours at speed mid?
        int hoursNeeded = 0;
        for (int pile : piles) {
            hoursNeeded += (pile + mid - 1) / mid;
        }
        // (pile + mid - 1) / mid = ceiling division using integer arithmetic

        if (hoursNeeded <= h) {
            hi = mid;       // This speed works! But can we go slower?
        } else {
            lo = mid + 1;   // Too slow, need to eat faster
        }
    }

    return lo;
}

// The monotonicity:
// K=1:  hours=27 > 8 → too slow
// K=2:  hours=15 > 8 → too slow
// K=3:  hours=10 > 8 → too slow
// K=4:  hours=8  = 8 → works!
// K=5:  hours=7  < 8 → works (but 4 is minimum)
//
// F F F T T T T T...
//       ↑ binary search finds this boundary

How to Identify "Binary Search on Answer"

Ask yourself:

Can I define a range of possible answers? (e.g., [1, max_value])
Can I write a function isFeasible(answer) that checks if an answer works?
Is the feasibility monotonic? (once True, stays True)

If all three → binary search on answer space.

More Examples

java
// Ship packages within D days → binary search on ship capacity
// Split array largest sum → binary search on the maximum sum
// Minimize maximum distance → binary search on the distance

// The template is always:
public int binarySearchOnAnswer() {
    int lo = minPossibleAnswer, hi = maxPossibleAnswer;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (isFeasible(mid)) {
            hi = mid;       // This works, try smaller (for "find minimum")
            // lo = mid + 1; // This works, try bigger (for "find maximum")
        } else {
            lo = mid + 1;   // Doesn't work, need bigger (for "find minimum")
            // hi = mid - 1; // Doesn't work, need smaller (for "find maximum")
        }
    }

    return lo;
}

Problems

875. Koko Eating Bananas - Medium
1011. Capacity To Ship Packages Within D Days - Medium
410. Split Array Largest Sum - Hard
4. Median of Two Sorted Arrays - Hard

Pattern 5: Search in Special Structures

Peak Element

java
// Find ANY peak (element greater than neighbors)
// Guaranteed: nums[-1] = nums[n] = -∞

public int findPeakElement(int[] nums) {
    int lo = 0, hi = nums.length - 1;

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] < nums[mid + 1]) {
            lo = mid + 1;   // Peak is to the right (going uphill)
        } else {
            hi = mid;       // Peak is here or to the left (going downhill)
        }
    }

    return lo;
}

// Why this works:
// If nums[mid] < nums[mid+1], there's an "uphill" to the right.
// Since nums[n] = -∞, the hill must come down eventually → peak exists on right.
// Similarly for the left.
// It's like climbing a mountain in fog — always walk uphill and you'll hit a peak.

Problems

162. Find Peak Element - Medium
240. Search a 2D Matrix II - Medium
981. Time Based Key-Value Store - Medium

Things You MUST Be Aware Of

1. The Infinite Loop Trap

java
// This loops forever when lo=5, hi=6:
while (lo < hi) {
    int mid = (lo + hi) / 2;  // mid = 5
    if (condition) {
        lo = mid;              // lo stays 5! Never progresses!
    }
}

// Fix: Always use lo = mid + 1 (not lo = mid)
// OR use hi = mid (not hi = mid + 1)
// At least one bound must STRICTLY change each iteration

2. Off-by-One Cheat Sheet

Finding FIRST >= target:  lo < hi, hi = mid,     lo = mid + 1
Finding LAST  <= target:  lo < hi, lo = mid + 1, hi = mid,     return lo - 1
Finding EXACT match:      lo <= hi, hi = mid - 1, lo = mid + 1

3. Empty Array

java
// Always handle nums = [] (length 0)
if (nums == null || nums.length == 0) {
    return -1;
}

4. Duplicates Change Everything

java
// In rotated array with duplicates [1,1,1,1,0,1,1]:
// When nums[lo] == nums[mid] == nums[hi], you can't tell which half is sorted
// Worst case degrades to O(n)
// Solution: skip duplicates with lo++ or hi--

5. Ceiling Division Without Extra Imports

java
// Ceiling of a/b:
(int) Math.ceil((double) a / b);   // Works but floating point issues

(a + b - 1) / b;                   // Integer only, always correct for positive a and b

Decision Guide

Sorted array, find exact value?
  └── Template 1: lo <= hi, return mid

Find first/last occurrence?
  └── Template 2: lo < hi, hi = mid or lo = mid + 1

Sorted then rotated?
  └── Check which half is sorted, search the correct half

"Find minimum X such that..."?
  └── Binary search on answer space

Peak finding?
  └── Compare mid with mid+1, go uphill

Matrix is sorted (each row sorted, row-by-row)?
  └── Treat as 1D array: row = mid / cols, col = mid % cols

Matrix sorted (rows sorted, cols sorted, but not row-by-row)?
  └── Staircase search from top-right or bottom-left (O(m+n), not binary search)

Binary Search

What is Binary Search?

Why O(log n)?

The Prerequisite

The Three Templates You Must Know

Template 1: Find Exact Match (lo <= hi)

Template 2: Find Left Boundary (lo < hi)

Template 3: Find Right Boundary

The Critical Differences

Why lo + (hi - lo) / 2 Instead of (lo + hi) / 2?

Pattern 1: Classic Binary Search

Find exact value in sorted array.

Search in 2D Matrix

Problems

Pattern 2: Finding Boundaries

What it is

The Mental Model

Step-by-Step: First and Last Position

Problems

Pattern 3: Rotated Sorted Array

What it is

The Key Insight

Find Minimum in Rotated Array

Problems

Pattern 4: Binary Search on Answer Space

What it is

When to use it

The Mental Model

Step-by-Step: Koko Eating Bananas

How to Identify "Binary Search on Answer"

More Examples

Problems

Pattern 5: Search in Special Structures

Peak Element

Problems

Things You MUST Be Aware Of

1. The Infinite Loop Trap

2. Off-by-One Cheat Sheet

3. Empty Array

4. Duplicates Change Everything

5. Ceiling Division Without Extra Imports

Decision Guide

Template 1: Find Exact Match (`lo <= hi`)

Template 2: Find Left Boundary (`lo < hi`)

Why `lo + (hi - lo) / 2` Instead of `(lo + hi) / 2`?