Почему мой двоичный поиск медленнее, чем линейный поиск?

Question

Я пытался закодировать двоичный поиск и линейный поиск и был шокирован, увидев, что двоичный поиск медленнее, чем линейный поиск, иногда даже в 2 раза. Пожалуйста, помогите мне. Вот мой код.

Код двоичного поиска:

def binary_search(array, target, n=0):
    l = len(array)-1
    i = l//2
    try:
        ai = array[i]
    except:
        return False
    if ai == target:
        n += i
        return (True, n)

    elif target >= ai:
        array = array[i+1:l+1]
        n += i + 1
        return binary_search(array, target, n)

    elif target <= ai:
        array = array[0: i]
        return binary_search(array, target, n)

Код линейного поиска

def linear_search(array, target):
    for i, num in enumerate(array):
        if num == target:
            return True, i

    return False

Код тестового примера:

import random 
import time
n = 10000000
num = sorted([random.randint(0, n) for x in range(n)])

start = time.time()
print(linear_search(num, 1000000))
print(f'Linear Search: {time.time() - start}')

start_new = time.time()
print(binary_search(num, 1000000))
print(f'Binary Search: {time.time() - start_new}')

Answer 1

Как сказал @khelwood, ваш код будет намного быстрее без нарезки.

def binary_search_no_slice(array, target, low, high):
    if low > high:
        return False
    mid = (low + high) // 2
    if array[mid] == target:
        return True
    elif array[mid] > target:
        return binary_search_no_slice(array, target, low, mid - 1)
    else:
        return binary_search_no_slice(array, target, mid + 1, high)

Добавлено ниже в ваш тестовый код.

start_new2 = time.time()
print(binary_search_no_slice(num, 1000000, 0, len(num) - 1))
print(f'Binary Search no slice: {time.time() - start_new2}')

Вот результат на моей машине (macOS Catalina, Corei7 2,8 ГГц, 8 ГБ ОЗУ)

False
Linear Search: 2.172485113143921
False
Binary Search: 0.56640625
False
Binary Search no slice: 2.8133392333984375e-05