Binary Search

Step 1 Understand it

Remember it by

Sorted, or 'yes, yes, yes, no, no'? Check the middle and throw half away.

Watch it happen

The idea

If you can ask a yes/no question whose answers flip only once across a range (sorted values, or 'is speed k fast enough?'), test the middle and discard the half that can't contain the answer. Each step halves the range: O(log n).

Picture it

flowchart LR
  R["range lo … hi"] --> M["mid = (lo + hi) // 2"]
  M --> Q{"does mid work?"}
  Q -->|"yes"| H["keep the left half<br/>hi = mid"]
  Q -->|"no"| L["keep the right half<br/>lo = mid + 1"]
  H & L --> C{"lo == hi?"}
  C -->|"no"| M
  C -->|"yes"| A["answer = lo"]

Analogy

Guessing a number from 1 to 100 with 'higher or lower' hints. Always guess the middle and you need at most 7 guesses.

Where the analogy breaks

The guessing game always has a number. Binary search on the answer needs a range of possible answers and a check that flips exactly once — you have to design that check yourself.

Step 2 Recognise it

Words that signal it

• Sorted array or matrix; 'O(log n)' required
• 'Minimum speed / capacity / time such that …' (search on the answer)
• 'Rotated sorted array'
• 'Find the first / last position where …'

Don't confuse it with

• Two Pointers: Sorted and looking for a pair → two pointers. Sorted and looking for one position or threshold → binary search.
• Greedy / linear scan: If checking one candidate answer is easy but the answer range is huge, binary search the answer instead of trying them all.

Gut check

Can I ask 'is the answer ≤ mid?' and get yes/no that flips once? → binary search.

How to recognise it in an interview

The input array is explicitly marked 'sorted' and requires 'Fast', 'Optimized', or 'O(log N)' search.

Step 3 The template

The general shape. Adapt it to each problem rather than learning one solution per problem.

def binary_search_on_answer(lo, hi):
    # find the smallest value in [lo, hi] for which ok(value) is True
    while lo < hi:
        mid = (lo + hi) // 2
        if ok(mid):        # mid works -> the answer is mid or smaller
            hi = mid
        else:              # mid fails -> the answer is bigger
            lo = mid + 1
    return lo

def ok(value):
    ...                    # your yes/no check

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

Common mistakes

• Infinite loops: with while lo < hi, set hi = mid (not mid − 1) and lo = mid + 1.
• Using lo <= hi with hi = mid, which loops forever when lo == hi.
• Searching the answer space without checking the check really flips only once.
• Calculating mid as (left + right) / 2, which can cause a serious integer overflow if the array is massive. Always use left + (right - left) / 2.

Step 4 Watch it run

Two problems, traced step by step exactly as the code runs.

def search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

import math

def min_eating_speed(piles, h):
    lo, hi = 1, max(piles)
    while lo < hi:
        k = (lo + hi) // 2
        hours = sum(math.ceil(p / k) for p in piles)
        if hours <= h:
            hi = k            # fast enough: try slower
        else:
            lo = k + 1        # too slow: go faster
    return lo

Step 5 Practise

Read each question and say the pattern and the trick out loud before you open the answer. Then solve it on LeetCode. Tick a problem once you've solved it on your own: it comes back for review tomorrow, then after 3, 7, 14 and 30 days, then every month, on the DSA page.

Easy

1. Mark "Binary Search" as solved Binary Search Easy

   Find a target's index in a sorted array in O(log n).

   Show answer

   Technique: Classic binary search

   The clue: Sorted + O(log n).

   The trick: Check the middle and discard the half that can't contain the target.

Medium

1. Mark "Search a 2D Matrix" as solved Search a 2D Matrix Medium

   Search a matrix whose rows are sorted and each row starts after the previous one ends.

   Show answer

   Technique: Binary search on a flattened index

   The clue: The whole matrix is one sorted list in disguise.

   The trick: Binary search index 0 … m·n − 1, mapping mid to row mid // n and column mid % n.

2. Mark "Koko Eating Bananas" as solved Koko Eating Bananas Medium

   Find the slowest eating speed that finishes all banana piles within h hours.

   Show answer

   Technique: Binary search on the answer

   The clue: 'Minimum speed such that …' — slow speeds fail, fast speeds pass.

   The trick: Search speeds 1 … max(piles); hours = sum of ceil(pile / k); keep the smallest speed that fits.

3. Mark "Find Minimum In Rotated Sorted Array" as solved Find Minimum In Rotated Sorted Array Medium

   Find the smallest number in a sorted array that has been rotated.

   Show answer

   Technique: Binary search comparing with the right end

   The clue: Sorted but rotated, O(log n).

   The trick: If nums[mid] > nums[right], the minimum is right of mid; otherwise it's at mid or to its left.

4. Mark "Search In Rotated Sorted Array" as solved Search In Rotated Sorted Array Medium

   Find a target in a rotated sorted array in O(log n).

   Show answer

   Technique: Binary search, find the sorted half

   The clue: Sorted but rotated, O(log n).

   The trick: One half around mid is always sorted; check whether the target lies inside that half to decide where to go.

5. Mark "Time Based Key Value Store" as solved Time Based Key Value Store Medium

   Store values with timestamps and return the latest value at or before a given time.

   Show answer

   Technique: Hash map + binary search on timestamps

   The clue: Timestamps arrive in increasing order, and you need 'the last one ≤ t'.

   The trick: Map each key to a list of (time, value); binary search for the rightmost time ≤ t.

Hard

1. Mark "Median of Two Sorted Arrays" as solved Median of Two Sorted Arrays Hard

   Find the median of two sorted arrays in O(log(m + n)).

   Show answer

   Technique: Binary search on a partition

   The clue: Two sorted arrays and a log-time requirement.

   The trick: Binary search how many items to take from the smaller array so that the left halves together hold half the items and every left item ≤ every right item.

What to say in the interview

'Because the array is already sorted, I can optimize the search from O(N) to O(log N) by using Binary Search.'

Follow-up prep

Can you use Binary Search on a Rotated Array?