Binary Search: Find a Target in a Sorted Array in O(log n)

Problem

You are given a list of integers sorted in ascending order with no repeated values, and a target integer. Return the index where the target sits, or -1 if it is not in the list. Your solution must run in logarithmic time, so a straight scan is not acceptable.

This is widely known as LeetCode 704 (Binary Search). It is the warm-up for every other problem on this pattern: if you can write it without an off-by-one bug, the harder variants are small changes.

Constraints for this version: the list holds 0 to 100,000 values, each between -1,000,000 and 1,000,000.

Examples

nums	target	Result	Why
[-8, -2, 4, 9, 15, 23]	9	3	9 is at index 3
[-8, -2, 4, 9, 15, 23]	5	-1	5 would fall between 4 and 9 but is absent
[42]	42	0	single element match
[]	7	-1	nothing to search

Approach 1: brute force

Walk the list from left to right and return the first index whose value equals the target. You can also stop early once you pass a value larger than the target, because the list is sorted.

def search_linear(nums, target):
    for i, value in enumerate(nums):
        if value == target:
            return i
        if value > target:
            break
    return -1

This is O(n) time and O(1) space. It ignores the sorted order beyond the early exit, which is exactly what the interviewer wants you to exploit.

Approach 2: optimal

Key insight. Because the list is sorted, one comparison with the middle element tells you which half the target must be in. Discarding half the candidates per step gives O(log n).

Invariant. With a closed range, the target, if present, is always at an index in [lo, hi]. The loop runs while that range is non-empty (lo <= hi).

Walkthrough for nums = [-8, -2, 4, 9, 15, 23], target = 15:

lo	hi	mid	nums[mid]	Decision
0	5	2	4	4 is less than 15, so lo = 3
3	5	4	15	match, return 4

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      # target can only be to the right
        else:
            hi = mid - 1      # target can only be to the left
    return -1

Interviewers sometimes ask for the recursive form too. It is the same logic with the range passed as arguments:

def search_recursive(nums, target, lo=0, hi=None):
    if hi is None:
        hi = len(nums) - 1
    if lo > hi:
        return -1
    mid = (lo + hi) // 2
    if nums[mid] == target:
        return mid
    if nums[mid] < target:
        return search_recursive(nums, target, mid + 1, hi)
    return search_recursive(nums, target, lo, mid - 1)

In production Python you would reach for the standard library bisect module, which finds the insertion point in O(log n):

from bisect import bisect_left

def search_bisect(nums, target):
    i = bisect_left(nums, target)
    return i if i < len(nums) and nums[i] == target else -1

Complexity. O(log n) time. The iterative version uses O(1) extra space; the recursive one uses O(log n) stack frames.

Tests

def check(fn):
    data = [-8, -2, 4, 9, 15, 23]
    for i, v in enumerate(data):
        assert fn(data, v) == i, (fn.__name__, v)
    for missing in [-100, -5, 0, 5, 10, 100]:
        assert fn(data, missing) == -1, (fn.__name__, missing)
    assert fn([], 7) == -1
    assert fn([42], 42) == 0
    assert fn([42], 41) == -1
    assert fn([1, 2], 1) == 0 and fn([1, 2], 2) == 1
    big = list(range(0, 200_000, 2))
    assert fn(big, 123_456) == 61_728
    assert fn(big, 123_457) == -1

for fn in (search_linear, search, search_recursive, search_bisect):
    check(fn)
print("all binary search tests passed")

Edge cases and pitfalls

• Loop condition. With a closed range [lo, hi] the loop must be lo <= hi. Writing lo < hi skips the last remaining candidate, so a one-element list fails.
• Moving the bounds. Always move past mid (mid + 1 or mid - 1). Setting lo = mid with a closed range can loop forever when lo and hi are adjacent.
• Overflow. Python integers do not overflow, but in Java or C++ (lo + hi) / 2 can. Write lo + (hi - lo) / 2 there and mention it.
• Empty input. hi starts at -1, the loop never runs, and you return -1 with no special case.
• Duplicates. This version returns some matching index, not necessarily the first. Use a lower-bound search when the position matters.

Where this shows up in data engineering

Binary search sits behind lookups on sorted data: finding which date partition or time bucket a timestamp belongs to with bisect, locating a key range in a sorted file, or bisecting a list of pipeline runs or commits to find the first one that produced bad data. Being able to reason about the invariant also helps when you read how storage engines search sorted indexes.