Paul's Python CoursePPC

Binary search on the answer

Not met yet

Sometimes there's no list to search, only a question whose answer is a number: the lightest load limit, the slowest speed, the fewest trips. If you can check one guess quickly, and the check switches from no to yes only once as the guesses grow, binary search the guesses themselves. Check the middle of what's possible, and throw away the half the answer can't be in. When the middle works, keep it, since it may be the answer: high = middle. A hundred million possible limits take about 27 checks.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks binary search only works on a list it can index, not on a range of possible answers tested with a yes-or-no check.
  • Thinks binary search on the answer needs the input sorted, rather than a check whose answer switches from no to yes only once.
  • Thinks the first guess that works is the answer, rather than a sign that the answer is that guess or smaller.
  • Thinks high = middle - 1 is right when the middle works, throwing away a guess that may be the answer.
  • Thinks a load limit lighter than the heaviest item can still work, given enough trips.

Where it comes up