Binary Search

Find a target in a sorted array.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Binary Search: Preserve the inclusive sorted interval that can still contain target 11.

Input and goalFind a target in a sorted array.

Initialize the candidate intervalFor target 11, left=0 and right=7 keep every index; middle=floor((0+7)/2)=3, whose value is 4.

left-90-3102middle4374115186right257

target11interval[0, 7]comparison4 < 11

Recognize it

The input is sorted and the task asks for an exact target position, so comparing one middle value can order the target relative to an entire half.

Keep true

Before every probe, if target 11 exists, its index is inside the inclusive interval [left, right]; every removed index is provably too small or too large.

Reuse it

For lower-bound, upper-bound, and insertion-position variants, first define what the interval promises, then choose whether middle is excluded or retained after each comparison.

Pattern: Binary search on indices.

Simple idea: Compare the middle value with the target. Keep only the half that may still contain the target.

def binary_search(nums: list[int], target: int) -> int:
   left, right = 0, len(nums) - 1

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

   return -1

Cost: $O(\log n)$ time and $O(1)$ space.