704. Binary Search (Easy)

Problem

Given an array nums sorted in ascending order and a target, return the index of target. If not present, return -1. The algorithm must run in $O(log n)$ time.

Example

• nums = [-1,0,3,5,9,12], target = 9 → 4
• nums = [-1,0,3,5,9,12], target = 2 → -1

LeetCode 704 · Link · Easy

Try it yourself

Python

▶ Run Python ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, linear scan

Ignore sortedness and scan linearly.

Python

def search(nums: list[int], target: int) -> int:
    for i, x in enumerate(nums):    # L1: scan every element, up to n iterations
        if x == target:             # L2: O(1) compare
            return i
    return -1

TypeScript

function search(nums: number[], target: number): number {
    for (let i = 0; i < nums.length; i++) {  // L1: scan every element, up to n
        if (nums[i] === target) return i;     // L2: O(1) compare
    }
    return -1;
}

Go

func search(nums []int, target int) int {
    for i, x := range nums {  // L1: scan every element, up to n iterations
        if x == target {      // L2: O(1) compare
            return i
        }
    }
    return -1
}

Swift

final class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        nums.firstIndex(of: target) ?? -1
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1/L2 (linear scan)	$O(1)$	n	$O(n)$ ← dominates

No early termination in the worst case (target not present or at the last position).

Complexity

• Time: $O(n)$, driven by L1 (linear scan ignoring sortedness).
• Space: $O(1)$.

Fails the problem’s $O(log n)$ requirement.

Approach 2: Recursive binary search

Divide the range and recurse.

Python

def search(nums: list[int], target: int) -> int:
    def helper(lo: int, hi: int) -> int:
        if lo > hi:                          # L1: base case, O(1)
            return -1
        mid = (lo + hi) // 2               # L2: O(1)
        if nums[mid] == target:             # L3: O(1) compare
            return mid
        if nums[mid] < target:              # L4: O(1) compare
            return helper(mid + 1, hi)      # L5: recurse on right half
        return helper(lo, mid - 1)          # L6: recurse on left half
    return helper(0, len(nums) - 1)

TypeScript

function search(nums: number[], target: number): number {
    function helper(lo: number, hi: number): number {
        if (lo > hi) return -1;                    // L1: base case, O(1)
        const mid = (lo + hi) >> 1;               // L2: O(1)
        if (nums[mid] === target) return mid;      // L3: O(1) compare
        if (nums[mid] < target) return helper(mid + 1, hi);  // L5: recurse right
        return helper(lo, mid - 1);               // L6: recurse left
    }
    return helper(0, nums.length - 1);
}

Go

func search(nums []int, target int) int {
    var helper func(lo, hi int) int
    helper = func(lo, hi int) int {
        if lo > hi {                          // L1: base case, O(1)
            return -1
        }
        mid := (lo + hi) / 2               // L2: O(1)
        if nums[mid] == target {            // L3: O(1) compare
            return mid
        }
        if nums[mid] < target {             // L4: O(1) compare
            return helper(mid+1, hi)        // L5: recurse on right half
        }
        return helper(lo, mid-1)            // L6: recurse on left half
    }
    return helper(0, len(nums)-1)
}

Swift

final class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        search(nums, target, low: 0, high: nums.count - 1)
    }

    private func search(_ nums: [Int], _ target: Int, low: Int, high: Int) -> Int {
        guard low <= high else { return -1 }
        let middle = low + (high - low) / 2
        if nums[middle] == target { return middle }
        if nums[middle] < target {
            return search(nums, target, low: middle + 1, high: high)
        }
        return search(nums, target, low: low, high: middle - 1)
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1-L4 (per frame)	$O(1)$	log n	$O(log n)$ ← dominates
L5 or L6 (recurse)	stack frame	log n	$O(log n)$ stack space

Each recursive call handles a half-size subproblem, so there are at most log n stack frames active at once.

Complexity

• Time: $O(log n)$, driven by L1-L4 (log n recursive levels, $O(1)$ work each).
• Space: $O(log n)$ recursion depth.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Iterative binary search (optimal)

Same halving, no recursion.

Python

def search(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums) - 1            # L1: O(1)
    while lo <= hi:                       # L2: loop, at most log n iterations
        mid = (lo + hi) // 2             # L3: O(1) midpoint
        if nums[mid] == target:           # L4: O(1) compare
            return mid
        if nums[mid] < target:            # L5: O(1) compare
            lo = mid + 1                  # L6: O(1) narrow right
        else:
            hi = mid - 1                  # L7: O(1) narrow left
    return -1

TypeScript

function search(nums: number[], target: number): number {
    let lo = 0, hi = nums.length - 1;    // L1: O(1)
    while (lo <= hi) {                    // L2: loop, at most log n iterations
        const mid = (lo + hi) >> 1;      // L3: O(1) midpoint
        if (nums[mid] === target) return mid;  // L4: O(1) compare
        if (nums[mid] < target) lo = mid + 1; // L6: O(1) narrow right
        else hi = mid - 1;                     // L7: O(1) narrow left
    }
    return -1;
}

Go

func search(nums []int, target int) int {
    lo, hi := 0, len(nums)-1             // L1: O(1)
    for lo <= hi {                        // L2: loop, at most log n iterations
        mid := (lo + hi) / 2            // L3: O(1) midpoint
        if nums[mid] == target {         // L4: O(1) compare
            return mid
        }
        if nums[mid] < target {          // L5: O(1) compare
            lo = mid + 1                 // L6: O(1) narrow right
        } else {
            hi = mid - 1                 // L7: O(1) narrow left
        }
    }
    return -1
}

Swift

final class Solution {
    func search(_ nums: [Int], _ target: Int) -> Int {
        var low = 0
        var high = nums.count - 1
        while low <= high {
            let middle = low + (high - low) / 2
            if nums[middle] == target { return middle }
            if nums[middle] < target {
                low = middle + 1
            } else {
                high = middle - 1
            }
        }
        return -1
    }
}

Where the time goes, line by line

Variables: n = len(nums).

Line	Per-call cost	Times executed	Contribution
L1 (init)	$O(1)$	1	$O(1)$
L2/L3/L4/L5 (loop body)	$O(1)$	log n	$O(log n)$ ← dominates
L6 or L7 (narrow)	$O(1)$	log n	$O(log n)$

Each iteration halves the search space from [lo, hi] to either [lo, mid-1] or [mid+1, hi]. Starting with n elements, after k steps we have n / 2^k elements remaining. The loop terminates when n / 2^k is less than 1, i.e., k exceeds log2(n).

Complexity

• Time: $O(log n)$, driven by L2 (loop halves the search space each iteration).
• Space: $O(1)$.

Note on mid = (lo + hi) // 2

In languages where integer overflow is a concern (C, C++, Java int), prefer mid = lo + (hi - lo) // 2 to avoid lo + hi overflowing. In Python, integers are arbitrary-precision, so (lo + hi) // 2 is safe.

Try this approach:

Python

▶ Run Python ↻ Reset

idle

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

TypeScript

▶ Run TS ↻ Reset

idle

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Go

▶ Run Go ↻ Reset

idle

Click Run Go to execute. Runs via the Go Playground API.

Swift notes

The recursive Swift approach adds $O(\log n)$ call-stack space. The iterative version keeps the same invariant in $O(1)$ extra space. Both receive [Int] by value, but read-only access shares copy-on-write storage and does not copy the elements.

Summary

Approach	Time	Space
Linear scan	$O(n)$	$O(1)$
Recursive binary search	$O(log n)$	$O(log n)$
Iterative binary search	$O(log n)$	$O(1)$

Memorize the iterative form, it’s the template for every other binary-search problem in this category.

Test cases

Python

# Quick smoke tests - paste into a REPL or save as test_704.py and run.
# Uses the optimal Approach 3 implementation.

def search(nums: list, target: int) -> int:
    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

def _run_tests():
    assert search([-1, 0, 3, 5, 9, 12], 9) == 4
    assert search([-1, 0, 3, 5, 9, 12], 2) == -1    # not present
    assert search([5], 5) == 0                        # single element found
    assert search([5], 3) == -1                       # single element not found
    assert search([-1, 0, 3, 5, 9, 12], -1) == 0     # first element
    assert search([-1, 0, 3, 5, 9, 12], 12) == 5     # last element
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

TypeScript

function search(nums: number[], target: number): number {
    let lo = 0, hi = nums.length - 1;
    while (lo <= hi) {
        const mid = (lo + hi) >> 1;
        if (nums[mid] === target) return mid;
        if (nums[mid] < target) lo = mid + 1;
        else hi = mid - 1;
    }
    return -1;
}

console.assert(search([-1, 0, 3, 5, 9, 12], 9) === 4);
console.assert(search([-1, 0, 3, 5, 9, 12], 2) === -1);    // not present
console.assert(search([5], 5) === 0);                        // single element found
console.assert(search([5], 3) === -1);                       // single element not found
console.assert(search([-1, 0, 3, 5, 9, 12], -1) === 0);    // first element
console.assert(search([-1, 0, 3, 5, 9, 12], 12) === 5);    // last element
console.log("all tests pass");

Go

package main

import "fmt"

func search(nums []int, target int) int {
    lo, hi := 0, len(nums)-1
    for 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
}

func main() {
    if search([]int{-1, 0, 3, 5, 9, 12}, 9) != 4     { panic("test 1") }
    if search([]int{-1, 0, 3, 5, 9, 12}, 2) != -1    { panic("test 2") } // not present
    if search([]int{5}, 5) != 0                        { panic("test 3") } // single element found
    if search([]int{5}, 3) != -1                       { panic("test 4") } // single element not found
    if search([]int{-1, 0, 3, 5, 9, 12}, -1) != 0    { panic("test 5") } // first element
    if search([]int{-1, 0, 3, 5, 9, 12}, 12) != 5    { panic("test 6") } // last element
    fmt.Println("all tests pass")
}

Related data structures

• Arrays, sorted-array access is the precondition for binary search

Related concepts

• Binary Search, the halving tactic for ordered spaces where one side can be discarded.
• Array Scans, the linear pass habit of carrying just enough state while reading each item once.