Python program: Binary search
Find a value in a sorted list by halving the search range each step.
The code
def binary_search(items, target): low, high = 0, len(items) - 1 steps = 0 while low <= high: steps += 1 mid = (low + high) // 2 if items[mid] == target: return mid, steps if items[mid] < target: low = mid + 1 else: high = mid - 1 return -1, steps data = list(range(0, 1_000_000, 3)) print(binary_search(data, 299_997)) print(binary_search(data, 5))
Output
(99999, 17) (-1, 18)
How it works
Each step throws away half of what is left, so even 333,334 items need at most about 19 steps. The list must be sorted. The bisect module provides this.
Python features used
Learn the ideas behind it in the free lesson Loops.