Skip to content
16-Week DSA Roadmap
LeetCode #704EasyProblem 6 of 8

Binary Search

Find a number in a sorted array by repeatedly checking the middle and throwing away the half that can't contain it.

  • Classic binary search

Before this, know: Arrays and indexes, Sorted order

The problem in plain English

You get an array nums that is sorted in ascending order (smallest to largest, no repeats) and a number target. Return the index (position, starting from 0) where target sits, or -1 if it isn’t there.

nums
  1. -10
  2. 01
  3. 32
  4. 53
  5. 94
  6. 125
nums = [-1, 0, 3, 5, 9, 12] and target = 9. The 9 is at index 4, so the answer is 4.

With the same array and target = 2, the answer is -1: there is no 2.

The one real rule: your solution must run in O(log n) time. Reading the array from left to right is too slow. We’ll see what O(log n) means and why the sorting makes it possible.

Before you code: think it through

A sorted array is the same game. Look at the middle item. If it’s too small, the target can only be to its right, because everything to its left is even smaller. If it’s too big, the target can only be to its left. Either way, half the array is gone after a single look.

16 left123456789101112131415168 left123456789101112131415163 left123456789101112131415161 left12345678910111213141516
Guessing 11 in 1–16. Purple is the guess, shaded cells are still possible, faded cells are ruled out. 16 → 8 → 4 → 2 → 1 candidates: at most 5 guesses.

Pause and think

nums = [2, 4, 6, 8, 10, 12, 14] and target = 12. You look at the middle item, 8 (index 3). Which indexes can you throw away, and why?

Approach 1: Brute force

Check every item from the left until you find the target or run out.

Brute force: check every item

nums = [1, 3, 5, 7, 9, 11, 13], target = 11

nums
  1. 10
  2. 31
  3. 52
  4. 73
  5. 94
  6. 115
  7. 136
variables
target
11
looks
1
result
—
  • Checking
  • Already checked
  • Target

Look #1: nums[0] = 1, not 11. Move on.

Step 1 / 6

Which line is running?

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

Brute force: linear search

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

Why is it slow?

It ignores the sorting completely. In the worst case (target missing, or at the very end) it looks at every item: 7 looks for 7 items, 1,000,000 looks for a million items. That’s O(n): the work grows in a straight line with the input. Not terrible, but the problem asks for O(log n), which for a million items is about 20 looks.

Binary search keeps a range lo..hi (two indexes, “low” and “high”) where the target must be if it exists. Each round it checks the middle index mid and moves lo or hi past it, cutting the range in half.

A promise that stays true on every trip around a loop is called a loop invariant. It’s how you convince yourself (and your interviewer) that the code is right.

Pattern

Classic binary search

Template

Use it when: the data is sorted (or has a yes/no answer that flips only once) and you need to find something faster than reading it all.

Signal words

  • “sorted array”
  • “O(log n)”
  • “find the index”
  • “search”
  • “first / last position”
  1. Set lo = 0 and hi = nums.length − 1: the whole array is still possible.
  2. While lo <= hi (the range has at least one item):
  3. Compute the middle: mid = lo + (hi − lo) // 2 (rounded down).
  4. If nums[mid] equals the target, return mid.
  5. If nums[mid] is smaller, the target is to the right: lo = mid + 1.
  6. If nums[mid] is bigger, the target is to the left: hi = mid − 1.
  7. If the loop ends, the range is empty: return -1.

Press Play. The shaded block is lo..hi, the part still in play. Watch it shrink by half every round, and the thrown-away parts fade out. In Not found, watch lo and hi cross at the end: that’s the loop’s exit.

Binary search: halve the range each round

nums = [1, 3, 5, 7, 9, 11, 13], target = 11

nums
  1. 10
  2. 31
  3. 52
  4. 73
  5. 94
  6. 115
  7. 136
variables
target
11
lo
0
hi
6
mid
—
nums[mid]
—
items left
7hi − lo + 1
rounds
0
result
—
  • Still possible (lo..hi)
  • mid, being checked
  • Thrown away
  • Target
  • Not the target

We look for 11. If it's anywhere, it's somewhere in nums[lo..hi]. At the start that's the whole array: lo = 0, hi = 6.

Step 1 / 5

Which line is running?

function search(nums, target) {  let lo = 0;Running now:   let hi = nums.length - 1; // the target, if present, is in nums[lo..hi]  while (lo <= hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] === target) {      return mid;    } else if (nums[mid] < target) {      lo = mid + 1; // mid is too small: drop it and everything left of it    } else {      hi = mid - 1; // mid is too big: drop it and everything right of it    }  }  return -1; // the range is empty: the target is not here}

The code, line by line

Classic binary search

function search(nums, target) {  let lo = 0;  let hi = nums.length - 1; // the target, if present, is in nums[lo..hi]  while (lo <= hi) {    const mid = lo + Math.floor((hi - lo) / 2);    if (nums[mid] === target) {      return mid;    } else if (nums[mid] < target) {      lo = mid + 1; // mid is too small: drop it and everything left of it    } else {      hi = mid - 1; // mid is too big: drop it and everything right of it    }  }  return -1; // the range is empty: the target is not here}
def search(nums, target):    lo, hi = 0, len(nums) - 1  # the target, if present, is in nums[lo..hi]    while lo <= hi:        mid = lo + (hi - lo) // 2        if nums[mid] == target:            return mid        elif nums[mid] < target:            lo = mid + 1  # mid is too small: drop it and everything left of it        else:            hi = mid - 1  # mid is too big: drop it and everything right of it    return -1  # the range is empty: the target is not here

JavaScript sets lo and hi on two lines and has closing } lines, so its line numbers run ahead of Python’s; we give both.

  • Line 1: define the function. (LeetCode wraps it as var search = function(nums, target), or def search(self, nums, target) inside class Solution in Python.)
  • Lines 2–3 (JS) / line 2 (Py): lo and hi start at the first and last index, so the whole array is in play. Python can set both at once: lo, hi = 0, len(nums) - 1.
  • Line 4 (JS) / line 3 (Py): lo <= hi means “the range has at least one item”. When lo == hi there is exactly one item left, and we must still check it, so it’s <=, not <.
  • Line 5 (JS) / line 4 (Py): the middle index. (hi − lo) // 2 is half the distance, rounded down (Math.floor in JS, // in Python). Adding it to lo lands in the middle. Writing (lo + hi) // 2 gives the same number; the lo + (hi − lo) // 2 form is a habit from languages like Java and C++, where lo + hi can be too big to store (an “overflow”).
  • Lines 6–7 (JS) / 5–6 (Py): found it. Return the index, not the value.
  • Lines 8–9 (JS) / 7–8 (Py): the middle is too small. It and everything left of it are ruled out, so lo jumps to mid + 1. The + 1 matters: mid has been checked.
  • Lines 10–11 (JS) / 9–10 (Py): the middle is too big, so hi jumps to mid − 1.
  • Line 14 (JS) / 11 (Py): lo > hi: no candidates left. Return -1.

Dry run

Trace nums = [1, 3, 5, 7, 9, 11, 13], target = 13. Each row is one round.

roundlohimidnums[mid]comparenext
106377 < 13lo = 4
24651111 < 13lo = 6
36661313 = 13return 6
nums = [1, 3, 5, 7, 9, 11, 13], target = 13

Look at round 3: lo and hi are both 6, so the range has one item. The loop still runs because the condition is lo <= hi. With lo < hi it would have stopped one round early and missed the 13.

Now a missing target, nums = [-1, 0, 3, 5, 9, 12], target = 2:

roundlohimidnums[mid]comparenext
105233 > 2hi = 1
2010-1−1 < 2lo = 1
311100 < 2lo = 2
end21lo > hireturn −1
nums = [-1, 0, 3, 5, 9, 12], target = 2

Complexity

Linear search

Time

O(n)

Up to one look per item: a million items, a million looks.

Space

O(1)

One index variable.

Binary search

Time

O(log n)

Each round halves the range. A million items: 1,000,000 → 500,000 → … → 1 takes about 20 rounds.

Space

O(1)

Just lo, hi and mid.

log₂ n (“log base 2 of n”) answers: how many times can I halve n before I reach 1? 8 → 4 → 2 → 1 is 3 halvings, so log₂ 8 = 3. For 1,000 it’s about 10; for 1,000,000 about 20; for a billion about 30. Double the input, and binary search needs just one more round.

Common mistakes and edge cases

What to say out loud, in this order:

  1. “The array is sorted, so I can rule out half of it with one comparison.”
  2. State the invariant: “if the target exists, it’s in nums[lo..hi].”
  3. Explain the boundaries: “lo <= hi because a one-item range still needs checking; mid ± 1 because mid is already checked.”
  4. Cost: O(log n) time, O(1) space; about 20 steps for a million items.
  5. Trace a one-item array and a missing target before saying you’re done.

Likely follow-up questions:

  • “Find the first or last position of a repeated value?” When you find it, don’t return: record it and keep searching left (or right).
  • “Where would the target be inserted?” When the loop ends, lo is exactly that index.
  • “Recursive version?” Same logic, with lo and hi as parameters. It uses O(log n) space for the call stack.

Related problems:

  • Search a 2D Matrix (this week): the same template on a grid.
  • Find Minimum in Rotated Sorted Array (this week): binary search when the array isn’t fully sorted.
  • Search in Rotated Sorted Array and Koko Eating Bananas (week 4): binary search on rotated data and “on the answer”.
  • The week 3 overview has the template and an off-by-one survival guide.