Search in Python

Implement linear search and iterative binary search, then watch binary search fail on unsorted input to understand why sorted data is a hard requirement.

Two search algorithms, side by side. Read through both before running — focus on the loop structure and the invariant each one maintains.

Linear search and binary search

Python — editable, runs in your browser

def linear_search(lst, target):
  # Scan left to right. Return the index if found, -1 if not.
  for i, x in enumerate(lst):
      if x == target:
          return i
  return -1

def binary_search(lst, target):
  # Maintain the invariant: if target is in lst it must be in lst[lo..hi].
  # Each iteration halves the search space. Requires lst to be sorted.
  lo = 0
  hi = len(lst) - 1
  while lo <= hi:
      mid = (lo + hi) // 2
      if lst[mid] == target:
          return mid
      elif lst[mid] < target:
          lo = mid + 1   # target must be in the right half
      else:
          hi = mid - 1   # target must be in the left half
  return -1

# --- sorted list: both work correctly ---
sorted_list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
print("=== Sorted list:", sorted_list, "===")
print("linear_search(7):", linear_search(sorted_list, 7))    # 3
print("binary_search(7):", binary_search(sorted_list, 7))    # 3
print("linear_search(6):", linear_search(sorted_list, 6))    # -1 (absent)
print("binary_search(6):", binary_search(sorted_list, 6))    # -1 (absent)

print()

# --- unsorted list: binary search gives wrong answers ---
unsorted_list = [9, 3, 15, 1, 7, 19, 5, 11, 17, 13]
target = 7
print("=== Unsorted list:", unsorted_list, "===")
print(f"Searching for {target}...")
li = linear_search(unsorted_list, target)
bi = binary_search(unsorted_list, target)
print("linear_search result:", li, "-> value at index:", unsorted_list[li] if li != -1 else "not found")
print("binary_search result:", bi, "-> value at index:", unsorted_list[bi] if bi != -1 else "not found (WRONG!)")

Reading the binary search loop

The loop maintains an invariant: if target is anywhere in the list, it must be somewhere in lst[lo..hi]. Each iteration:

Computes the midpoint — (lo + hi) // 2 avoids the integer overflow that (lo + hi) / 2 can cause in languages with fixed-width integers.
Compares lst[mid] to target.
Narrows the range by moving lo up or hi down — always preserving the invariant.

When lo > hi, the range is empty: target is not in the list.

Why binary search fails on unsorted data

In the unsorted example above, binary_search compares the middle element and then discards one half — but on unsorted data, the target might be in the discarded half. The algorithm has no way to know. It gives a confident-looking answer that is simply wrong.

This is not a bug to be fixed — it is a precondition violation. Always sort before calling binary search, or use linear search if you cannot guarantee order.

Python's standard library provides bisect.bisect_left(sorted_list, target) for binary search. Use it in production code — it is correct and tested. The hand-rolled version above is for learning the algorithm.

Where to go next

Next: Lab: search — time linear vs binary search on growing inputs, implement a count-using-search function, and try a bonus recursive flatten.

Finished reading? Mark it complete to track your progress.

Linear search and binary search

Reading the binary search loop

Why binary search fails on unsorted data

Where to go next

On this page