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.pyOutput
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.