LC 704 — Binary Search · Binary Search

Problem

What are we solving?

Problem Statement

Given an array of integers nums sorted in ascending order, and an integer target, write a function to search for target in nums. Return the index if found, otherwise return -1. You must write an algorithm with O(log n) runtime.

Example 1

Input:nums = [-1, 0, 3, 5, 9, 12], target = 9

Output:4

Example 2

Input:nums = [-1, 0, 3, 5, 9, 12], target = 2

Output:-1

Intuition

Halve the search space every single step

A sorted array lets us make a binary decision at every step: if the middle element is too small, the target must be to the right. If too large, it must be to the left. If equal, we're done. Each step cuts the remaining search space in half.

With 1 billion elements, binary search finds any value in at most 30 comparisons. Linear search needs up to 1,000,000,000.

nums = [-1, 0, 3, 5, 9, 12] · target = 9

i=0-1

i=10

i=23

i=35

i=49

i=512

Target 9 lives at index 4. Binary search homes in without checking every element.

Step-by-step walkthrough

1

left=0, right=5 → mid=2, nums[2]=3

3 < 9 → target is to the right. left = 3.

2

left=3, right=5 → mid=4, nums[4]=9

9 == 9 → Found! Return index 4.

!

Never write (left + right) / 2. When both are near Integer.MAX_VALUE the sum overflows. Always use left + (right - left) / 2. Python integers are arbitrary precision so this isn't an issue there, but the habit is worth keeping.

Solution

The canonical template

class Solution {
    public int search(int[] nums, int target) {
        int left = 0;
        int 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;
    }
}

class Solution:
    def search(self, nums: list[int], target: int) -> int:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = left + (right - left) // 2

            if nums[mid] == target: return mid
            elif nums[mid] < target: left = mid + 1
            else: right = mid - 1

        return -1

Complexity

Time

O(log n)

Halves the range each step. log₂(10⁹) ≈ 30 steps.

Space

O(1)

Three integer pointers — no extra memory.