Paul's Python CoursePPC

Binary search

Not met yet

Binary search finds an item in a sorted list by looking in the middle and throwing away the half it can't be in, again and again. Each look halves what's left, so a million items take at most 20 looks: O(log n). Keep low and high as the first and last places it could still be, move them past middle each time, and stop only when low passes high. On an unsorted list it gives wrong answers without complaint.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks binary search finds things in an unsorted list, only more slowly or not at all, rather than giving wrong answers.
  • Thinks binary search looks at half the items, so takes about n / 2 looks.
  • Thinks a binary search can stop when low and high are the same position, before looking there.
  • Thinks low = middle works as well as low = middle + 1 in a binary search.

Where it comes up