Binary Search (and its Variants)Step 1 of 5

Classic Binary Search

12345

Step 1 — Classic Binary Search

A sorted list lets you find any value without scanning it end to end. Binary search keeps a window [lo, hi] of candidate indices, looks at the middle element, and throws away the half that cannot contain the target. Each step halves the window, so a list of a million items is searched in about twenty comparisons.

Implement search(arr, target):

  • arr is a list sorted in ascending order.
  • Return the index where target is found, or -1 if it is not present.
  • Use the inclusive window lo = 0, hi = len(arr) - 1 and loop while lo <= hi.
  • Compare arr[mid] to target: on a match return mid; if arr[mid] is too small move lo up; otherwise move hi down.

This is the foundation every later step builds on, so make the boundaries exact.

Hints
Starter code
def search(arr, target):
    """Return the index of target in sorted arr, or -1 if absent."""
    # TODO: binary search. Track lo and hi, compare arr[mid] to target.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

OverviewNext step