Basic

Halving the work

A loop that cuts the remaining work in half each turn does only about log n steps. That is why searching a sorted list is fast.

What you will see

About 2 min of reading

Try It

Halve a range and count the steps.

Halve 64 to one.

n = 64 steps = 0 while n > 1: n //= 2 steps += 1 print(steps)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Binary search for 9.

a = [1, 3, 5, 7, 9, 11, 13] target = 9 lo, hi, steps = 0, len(a) - 1, 0 while lo <= hi: mid = (lo + hi) // 2 steps += 1 if a[mid] == target: break if a[mid] < target: lo = mid + 1 else: hi = mid - 1 print(a[mid], steps)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

9 3

Thirds of 81.

n = 81 steps = 0 while n > 1: n //= 3 steps += 1 print(steps)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

Halving a million.

n = 1000000 steps = 0 while n > 1: n //= 2 steps += 1 print(steps)

Before you run it, say out loud what it will print. Then open the answer.

What it prints

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

Cutting the remaining work by a fixed fraction each turn costs logarithmic steps. Binary search halves a sorted range.

1 have ordered data

↓

2 compare the middle

↓

3 throw away a half

↓

4 steps grow logarithmically

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.

n = 64 sets nothing on screen

steps = 0 sets nothing on screen

while n > 1: sets nothing on screen

n //= 2 sets nothing on screen

steps += 1 sets nothing on screen

print(steps) 6

Why this works

Halving is logarithmic

Any loop that cuts the remaining work by a fixed fraction costs logarithmic steps. The base of the fraction is a constant.

Order makes it possible

Halving only helps when the data is ordered. Without order a middle item tells you nothing.

Examples

Halve until one

n = 64
steps = 0
while n > 1:
    n //= 2
    steps += 1
print(steps)

Sixty four halves to one in six steps. Two to the six is sixty four.

Binary search

a = [1, 3, 5, 7, 9, 11, 13]
target = 9
lo, hi, steps = 0, len(a) - 1, 0
while lo <= hi:
    mid = (lo + hi) // 2
    steps += 1
    if a[mid] == target:
        break
    if a[mid] < target:
        lo = mid + 1
    else:
        hi = mid - 1
print(a[mid], steps)

Each compare throws away half the range. Seven items need three steps.

Sorted is required

a = [3, 1, 2]
print(a)

Halving only works when the order is known. An unsorted list gives no information from a middle item.

Log grows slowly

for n in (1000, 1000000):
    k, s = n, 0
    while k > 1:
        k //= 2
        s += 1
    print(n, s)

A million items need about nineteen steps. The class is logarithmic.

Divide by three

n = 81
steps = 0
while n > 1:
    n //= 3
    steps += 1
print(steps)

Cutting by three is still logarithmic. The base only changes a constant factor.

Log with a linear pass

n = 8
steps = 0
for i in range(n):
    steps += 1
k = n
while k > 1:
    k //= 2
    steps += 1
print(steps)

A linear pass plus a halving loop is n plus log n. The linear part dominates.

Steps for a million

n = 1000000
steps = 0
while n > 1:
    n //= 2
    steps += 1
print(steps)

Nineteen steps for a million items. A linear scan of the same costs a million.

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.

← Nested loops multiply

Previous Lesson

Nested loops multiply

Next Lesson

Best, worst, and average

Best, worst, and average →