Syllabus Lesson 57 of 141 · Speed without the cache
Speed without the cache

Bound the search

Why it matters "Find the best one" sounds like "look at every one". Often a simple bound tells you that nothing further down the list can win, and you can stop.

An order can ship from any of 50,000 warehouses. The list arrives sorted by distance from the customer, nearest first. Shipping costs 12p per km, and each warehouse adds its own handling fee, which is never more than 5,000p. Each warehouse record sits behind a slow stock service, so every record you read costs.

(distance_km, fee, name)   # cost = distance_km * 12 + fee
Your turn

Write cheapest(tape). tape is a non-empty Tape of (distance_km, fee, name) records sorted by distance_km ascending. Cost is distance_km * 12 + fee, and every fee is between 0 and 5,000. Return the name of the cheapest warehouse; if costs tie, the nearer one; if that ties too, the one earlier in the list. Budget: read at most 2,000 records out of 50,000. len(tape) is free.

Spotted a problem in this lesson? Report it · Ask about this lesson

This exercise opens soon

Finish the lesson before it and this one unlocks. The whole course is free, no account needed, and you can read this lesson right now.

Start at lesson 1 Back to syllabus