This Binary Search lesson is for a beginner. Read the short notes, run each example, then change one name or number and run it again.
Binary search cuts a sorted list in half on every step. It is wrong on an unsorted list.
Compare the middle item with the target and keep the half that can still hold it.
Example 1: Start here
The list must be sorted before the first call.
def search(items, target): # define the function; it runs when you call it
lo, hi = 0, len(items) - 1 # one value for each name on the left
while lo <= hi: # keep repeating while this stays true
mid = (lo + hi) // 2 # a tuple; a fixed group of values
if items[mid] == target: # run the indented lines only when this is true
return mid # send this value back to the caller
if items[mid] < target: # run the indented lines only when this is true
lo = mid + 1 # the result of this math
else: # runs when the test above was false
hi = mid - 1 # the result of this math
return -1 # send this value back to the caller
print(search([2, 4, 7, 9], 7))
Example 2: Walk the values
Binary Search starts by visiting one value at a time. Read the printed lines from top to bottom.
values = [29, 3, 11, 7] # a list; the values stay in this order
for value in values: # repeat the indented lines once per value
print(value)
Example 3: Keep the largest
Many data-structure lessons reduce a list to one answer. This one remembers the largest number seen so far.
values = [29, 3, 11, 7] # a list; the values stay in this order
best = values[0] # the first value
for value in values: # repeat the indented lines once per value
if value > best: # run the indented lines only when this is true
best = value # another name for the same value
print(best)
Example 4: Search for a target
A search asks one yes-or-no question: is the target in the collection? Binary Search builds on that question.
values = [3, 29, 11] # a list; the values stay in this order
target = 29 # a whole number
print(target in values) # in is True when the value is found
The list must be sorted before the first call.
