Data structures problem 7 of 30

Binary search, by hand

Data structures
Easy

Write search(nums, target) that returns the index of target in a sorted list, or -1 if it is not there. It must run in O(log n). No bisect.

search([1, 3, 5, 7, 9], 7)   # 3
search([1, 3, 5, 7, 9], 4)   # -1

Show hint

Keep two indices, lo and hi, for the part of the list that could still contain the target. Look at the middle and throw away half.

Show solution

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

Each loop halves the range, giving O(log n). The common bugs are using lo < hi (which misses one-element ranges) and setting lo = mid instead of mid + 1 (which can loop forever).

Want a problem like this every day? See today's problem and keep a streak going.