Binary Search#

Problem#

Given a sorted array of distinct integers and a target value, return the index of the target if it is present, or -1 if it is not.

Example#

Array [-1, 0, 3, 5, 9, 12], target 9 returns 4. Target 2 returns -1 because it is not in the array.

Brute force#

Scan every element and compare against the target. That is O(n) and ignores the fact that the array is sorted.

Optimal approach#

Because the array is sorted you can discard half the remaining range on every comparison. Keep two pointers, low and high, bounding the region that could still contain the target. Look at the middle element. If it equals the target you are done. If it is smaller, the target can only be to the right, so move low past the middle. If it is larger, move high before the middle. Repeat until the pointers cross. Compute the midpoint as low + (high - low) // 2 to avoid integer overflow in languages where that matters, and to read clearly here.

Solution#

 1def binary_search(nums: list[int], target: int) -> int:
 2    low, high = 0, len(nums) - 1
 3    while low <= high:
 4        mid = low + (high - low) // 2
 5        if nums[mid] == target:
 6            return mid
 7        if nums[mid] < target:
 8            low = mid + 1
 9        else:
10            high = mid - 1
11    return -1
12
13
14print(binary_search([-1, 0, 3, 5, 9, 12], 9))  # 4
15print(binary_search([-1, 0, 3, 5, 9, 12], 2))  # -1

Complexity#

• Time: O(log n), the range halves each iteration.
• Space: O(1), only two pointers.

Binary search underpins many patterns. Keep practicing with the 60-day challenge.