[Python] Binary versus linear search on ordered arrays, why is binary search taking longer...

I'm trying to set up an experiment where I compare search algorithms on ordered arrays.

I expected that the binary search implementation would be faster than the linear search method for large search spaces but I'm getting the opposite results.

Here is a minimal reproducible example:

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)


I expect that there is something wrong with my implementation of binary search. Is anyone able to spot this issue?

I was struggling with figuring out how to return the correct index (if any) for binary search so I feel like it's something to do with my implementation.

Is anyone able to help at all?

I would expect that the time taken for binary search at large search spaces to be faster than the linear search, but I'm getting the opposite results.

Continue reading...