search_algorithms.py

import numpy as np

# a decorator to measure the time of a function
def measure_time(func):
    import time
    def wrapper(*args, **kwargs):
        start = time.time()
        result = func(*args, **kwargs)
        end = time.time()
        print(f"{func.__name__} took {end - start} seconds")
        return result
    return wrapper

def is_sorted(a):
    for i in range(len(a)-1):
        if a[i] > a[i+1]:
            return False
    return True


@measure_time
def sequential_search(a, key):
    for i in range(len(a)):
        if a[i] == key:
            return i
    return -1

def recursive_sequential_search_core(a, key, i):
    if i >= len(a):
        return -1
    if a[i] == key:
        return i
    return recursive_sequential_search_core(a, key, i+1)

@measure_time
def recursive_sequential_search(a, key):
    return recursive_sequential_search_core(a, key, 0)

@measure_time
def binary_search(a, key):
    assert is_sorted(a), "The list must be sorted for binary search algorithm to work"
    low = 0
    high = len(a) - 1
    while low <= high:
        mid = (low + high) // 2
        if a[mid] == key:
            return mid
        elif a[mid] < key:
            low = mid + 1
        else:
            high = mid - 1
    return -1

def recursive_binary_search_core(a, key, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if a[mid] == key:
        return mid
    elif a[mid] < key:
        return recursive_binary_search_core(a, key, mid+1, high)
    else:
        return recursive_binary_search_core(a, key, low, mid-1)

@measure_time
def recursive_binary_search(a, key):
    assert is_sorted(a), "The list must be sorted for binary search algorithm to work"
    return recursive_binary_search_core(a, key, 0, len(a)-1)

@measure_time
def get_sorted_list_and_mapping(a):
    sorted_a = a.copy()
    sorted_a.sort()
    mapping = {}
    for i in range(len(sorted_a)):
        mapping[sorted_a[i]] = a.tolist().index(sorted_a[i])
    return sorted_a, mapping



    # choose a random key

import sys
sys.setrecursionlimit(1000000)

a = np.arange(100000)
np.random.shuffle(a)

key = np.random.choice(a)
print(key)
print(sequential_search(a.copy(), key))
print(recursive_sequential_search(a.copy(), key))

sorted_a, mapping = get_sorted_list_and_mapping(a)

sorted_idx = binary_search(sorted_a.copy(), key)
print(mapping[sorted_a[sorted_idx]])


sorted_idx = recursive_binary_search(sorted_a.copy(), key)
print(mapping[sorted_a[sorted_idx]])