Linear search
Linear search starts at the front and checks each item in turn until it finds the target. Finding 42 here takes 10 comparisons. On a list of n items it may need all n, so it is O(n).
Binary search
Binary search only works on a sorted list. It keeps two pointers, low and high, around the part where 42 could still be. At the start that is the whole list, so low = 0 and high = 15.
mid = (0 + 15) // 2 = 7, because // divides and rounds down. a[7] is 33, less than 42. The list is sorted, so every item left of it is smaller too: 42 can only be to the right.
So low = mid + 1 = 8. One comparison ruled out 8 items, half the list. The search goes on between low and high: items 8 to 15.
mid = (8 + 15) // 2 = 11. a[11] is 51, more than 42. This time everything right of the middle is too big, so the target must be on the left.
So high = mid - 1 = 10. Only items 8, 9 and 10 are left. The + 1 and - 1 matter: mid was already checked, so the next range leaves it out.
mid = (8 + 10) // 2 = 9, and a[9] is 42, so it returns 9. Binary search needed 3 comparisons where linear search needed 10. If low ever passes high, the target is not there and it returns -1.
Speed and pitfalls
Each comparison halves what is left: 16, 8, 4, 2, 1. So 16 items need at most 5 comparisons. A million items need at most 20, because 2 to the power 20 is more than a million. That is O(log n).
Small slips break it. With while low < high, a range of one item is never checked, so searching [5] for 5 fails. With low = mid instead of mid + 1, the range can stop shrinking and the loop never ends.
Python ships binary search in the bisect module. bisect_left(a, 42) returns 9, the first place 42 could go and keep a sorted. Check that a[9] == 42 before you trust it, and use it only on sorted lists.
Try it in the Python prompt
;; step 1/10 · Linear search: one by one >>> def linear_search(a, target): ... for i in range(len(a)): ... if a[i] == target: ... return i ... return -1 ... >>> a = [3, 7, 11, 15, 19, 24, 28, 33, 38, 42, 47, 51, 56, 61, 67, 72] >>> linear_search(a, 42) # looks at a[0], a[1], ... a[9] 9 >>> 42 in a # also a linear search True
The drawing counts one comparison per item looked at. The code tests a[mid] == target and then a[mid] < target, so in Python terms that can be two tests per item; the count still grows as log n. This binary search looks at no more than floor(log2 n) + 1 items, whether the target is there or not. For n = 16 that is 5; for n = 1,000,000 it is 20, because 2^19 = 524,288 is not more than a million but 2^20 = 1,048,576 is.