704 - Binary Search

Difficulty: Easy | Pattern: Binary Search | Company tags: Google, Amazon, Facebook

Problem Statement

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, return its index. Otherwise, return -1.

You must write an algorithm with O(log n) runtime complexity.

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

Algorithm Flow

Solution

def search(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

Dry Run

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

left	right	mid	nums[mid]	action
0	5	2	3	3 lt 9, left=3
3	5	4	9	match! return 4

4 ✓

Two Templates to Know

Template 1 (above): left <= right, returns when found. Good for exact matches.

Template 2 (find boundary): left < right, keeps mid in range. Good for "find first/last satisfying condition."

# Find first position where condition is True
def binary_search_boundary(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] >= target:
            right = mid
        else:
            left = mid + 1
    return left  # first index where nums[index] >= target

Common Mistakes

• Using mid = (left + right) // 2 can overflow in languages with fixed integers. Use mid = left + (right - left) // 2.
• Off-by-one: right = mid vs right = mid - 1 depending on template.

Complexity

• Time: O(log n)
• Space: O(1)