Exercise 1 solution

Prediction: linear search reaches the last item, so it compares every item: n comparisons.
Binary search needs about log2(n) + 1 comparisons.

    for n in (100, 100000):
        data = list(range(n))
        print(n, linear_count(data, n - 1), binary_count(data, n - 1))

Expected shape of the result:
    100     linear 100 comparisons      binary about 7
    100000  linear 100000 comparisons   binary about 17

(Run for n = 10, 1000 and 1000000 the same functions gave 10/4, 1000/10 and
1000000/20 comparisons for a target at the end.)

Lesson: multiplying the data by 1000 multiplied linear search's work by 1000,
but added only about 10 steps to binary search.