Бинарный и линейный поиск по упорядоченным массивам, почему бинарный поиск занимает больше времени, чем линейный поиск? ⇐ Python

[Anonymous]

Я пытаюсь организовать эксперимент, в котором я сравниваю алгоритмы поиска на упорядоченных массивах. Пространства, но я получаю противоположные результаты. < /p>
Вот минимальный воспроизводимый пример: < /p>
import time
import random
''''
search algorithms for ORDERED arrays

linear search
binary search

'''
def timeit(f):
def wrapper(*args, **kwargs):
st = time.time()
y =f( *args,**kwargs)
ft = time.time()
print(f.__name__,'\n', ft-st, 'seconds')
print("searching for value: ", args[1], f"\nsize of search space: {len(args[0])} elements", f'\nfound? @ idx={y}')
if y:
print("verifying...")
print(f"x[{y}]={x[y]}\n\n")
return y
return wrapper

def sample_array(n=10000000, type=['classic','ordered'][1]):
if type == 'classic':
return list(random.choices( list(range(1,101)),k=n))
if type == 'ordered':
return sorted(list(random.choices( list(range(1,101)),k=n)))

@timeit
def linear_search(x,val):
'''
x : ordered array
val: search value
'''
if x[0] > val or val > x[-1]: # check if out of bounds
return None
for (idx, _val) in enumerate(x): # check part of array

if _val == val:
return idx
else:
return None

@timeit
def binary_search(x,val):
'''
x: ordered array
val: search value
'''
if x[0] > val or val > x[-1]: # check if out of bounds
return None
x = list(enumerate(x)) # tracking indices of total array

while True:
mid = len(x)//2
if x[mid][1] == val:
return x[mid][0]

elif val < x[mid][1]:
x = x[:mid]

elif val > x[mid][1]:
x = x[mid:]

# base case
if len(x) == 2:
if all([_x[1] != val for _x in x ] ):
return None

x = sample_array()
linear_search(x,68)
idx= binary_search(x,68)
< /code>
Я ожидаю, что что -то не так с моей реализацией бинарного поиска. Кто -нибудь может определить эту проблему? < /p>
может ли кто -нибудь вообще помочь? Поиск, но я получаю противоположные результаты.

Подробнее здесь: https://stackoverflow.com/questions/794 ... king-longe