I’ve been trying to use parametrised decorators and time function for becnhmark binary search vs linear algorithms running time and I don't understand, why with list size == 100m binary search runs 0.000014 sec and linear search runs 4.904940 sec. Where is my mistake? Or is it a normal speed for modern cpus? A few hours ago I set list size to 1b and run script. My pc frozen on a few hours and I forced a reboot it. PS My CPU is I5 9th Gen.

import time


def second_outer(*dargs, **dkwargs):
    def outer(func):
        def inner(*args, **kwargs):
            print(*dargs, **dkwargs)
            start = time.time()
            func_result = func(*args, **kwargs)
            print('Call function %s with duration %f' % (func.__name__, time.time() - start))
            return func_result
        return inner
    return outer


arr = [i for i in range(1, 100000000)]


@second_outer('binary search')
def binary_search(arr, item):
    start = 0
    end = len(arr) - 1
    while start <= end:
        middle = (start   end) // 2
        guess = arr[middle]
        if guess == item:
            return middle
        elif guess > item:
            end = middle - 1
        else:
            start = middle   1
    return None


@second_outer('linear search')
def linear_search(arr, item):
    start = 0
    end = len(arr)
    for i in range(start, end):
        if arr[i] == item:
            return i
    return None


print(binary_search(arr, arr[-1]))
print(linear_search(arr, arr[-1]))

CodePudding user response：

Looks like there is no error in your code)

It simply finds a number in in 27 iterations

Call function binary_search with duration 0.000125

This is for 1B numbers. Probably you had an error a couple of hours ago when your PC froze

CodePudding user response：

Binary search runs on log(n) and linear search runs on n. That means that the first one only has to do log(n) iterations, and log2(100000000) = 26.5754. So you are basically comparing 27 iterations vs 100m.