Halving is the power
Each look throws away half the row. That halving is why the count of looks is the log of the size, not the size itself.
Binary search
Binary search looks at the middle of a sorted row and keeps only the half that can hold the value. Each step halves the search, so a million items take about twenty looks.
What you will see
1
About 3 min of reading
Quick check
Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.
Try It
Search a sorted row by halving.
1
Find 7 by halving.
nums = [1, 3, 5, 7, 9]
target = 7
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print(mid)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
3
2
Show looks for a million.
import math
print(round(math.log2(1000000)))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
20
3
Report a missing value.
nums = [1, 3, 5]
lo, hi = 0, len(nums) - 1
found = False
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == 4:
found = True
elif nums[mid] < 4:
lo = mid + 1
else:
hi = mid - 1
print(found)
Before you run it, say out loud what it will print. Then open the answer.
What it prints
False
4
Find the first 2.
import bisect
nums = [1, 2, 2, 2, 3]
print(bisect.bisect_left(nums, 2))
Before you run it, say out loud what it will print. Then open the answer.
What it prints
1
Put it in order
Before you write anything, put these lines back in the right order. Click a line to move it up one step. This support step is easier than writing code from scratch, and it is here to make the last example stick.
Data Flow
Binary search keeps the half of a sorted row that can hold the value, halving each step, so a million items take about twenty looks.
1
sorted row
↓
2
check middle
↓
3
keep one half
↓
4
about log n looks
Line by line
Read the first example one line at a time. A line that prints shows what appears on screen; the rest set things up quietly.
nums = [1, 3, 5, 7, 9]
sets nothing on screen
target = 7
sets nothing on screen
lo, hi = 0, len(nums) - 1
sets nothing on screen
while lo <= hi:
sets nothing on screen
mid = (lo + hi) // 2
sets nothing on screen
if nums[mid] == target:
sets nothing on screen
break
sets nothing on screen
if nums[mid] < target:
sets nothing on screen
lo = mid + 1
sets nothing on screen
else:
sets nothing on screen
hi = mid - 1
sets nothing on screen
print(mid)
3
Why this works
When you have a choice
Sort cost versus search cost
Sorting once costs n log n. If you then do many searches, each log n, sorting first still beats scanning n for every search.
Examples
Halve the row
nums = [1, 3, 5, 7, 9]
target = 7
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
print(mid)The middle tells which half to keep. The row is cut in half every step.
Count the looks
import math
print(round(math.log2(1000000)))A million items halve about twenty times. Twenty looks find a value in a million.
Not found
nums = [1, 3, 5]
lo, hi = 0, len(nums) - 1
found = False
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == 4:
found = True
elif nums[mid] < 4:
lo = mid + 1
else:
hi = mid - 1
print(found)When lo passes hi the value is absent. The loop ends without a match.
Sorted is required
nums = [3, 1, 2]
print(nums)Binary search needs a sorted row. On an unsorted row the half you keep may not hold the value.
bisect again
import bisect
nums = [1, 3, 5, 7]
i = bisect.bisect_left(nums, 5)
print(nums[i] == 5)bisect is binary search in the library. It returns the spot, and the item there answers the question.
Find the first match
import bisect
nums = [1, 2, 2, 2, 3]
print(bisect.bisect_left(nums, 2))bisect_left lands on the first 2. That is the left edge of the run of equal values.
Insertion point
import bisect
nums = [1, 4, 7]
print(bisect.bisect_left(nums, 5))The spot where 5 belongs is returned even though 5 is absent. That index is where to insert.
Twenty for a million
import math
print(math.log2(1000000) < 20)Halving a million reaches one in twenty steps. That is why sorted search scales.
Words this lesson uses
Each one is defined here on this site. Open the entry for the full definition and the other words it points at.
← Quicksort
Previous Lesson
Quicksort