Binary Search

Problem

Given a sorted array of distinct integers and a target value, return the index of the target if it exists, otherwise return -1. You must do it faster than a linear scan.

My notes

Signal

Sorted input plus "find a value" is the plainest possible trigger: every comparison against the midpoint eliminates half the remaining candidates, so you never need to look at most of the array.

Approach

Keep a left/right window over the whole array. Look at the midpoint: if it's the target, you're done; if the target is smaller, the answer can only be to the left, so shrink right; if larger, shrink left. Stop when the window is empty.

Skeleton

left, right = 0, len(nums) - 1
while left <= right:
    mid = (left + right) // 2
    if nums[mid] == target: return mid
    if nums[mid] < target: left = mid + 1
    else: right = mid - 1
return -1

Solution

def search(nums: list[int], target: int) -> int:
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Complexity

O(log n) time — the search window halves each iteration. O(1) space.

Pitfalls

mid = (left + right) // 2 can overflow in languages with fixed-width integers (use left + (right - left) // 2); not an issue in Python, but worth naming if the interviewer asks about other languages.
Off-by-one on the loop condition: use left <= right, not left < right, or you'll miss the case where the window has exactly one element left.
Forgetting to move left/right past mid (mid + 1 / mid - 1, not mid) causes an infinite loop.