Searching Algorithms

import random

random.seed(10)

l = list(set([random.randint(0, 10000000) for i in range(10000000)]))
sorted_l = sorted(l)
len(l)

6319528

Linear Search

def linear_search(l, element):
    length = len(l)
    for i in range(length):
        if l[i] == element:
            return True
    return False

linear_search(l, 3), linear_search(l, 13)

(True, False)

Binary Search

def binary_search(arr, ele):
    low: int = 0
    high: int = len(arr) - 1

    while low <= high:
        mid = int(low + (high - low) / 2)
        if arr[mid] == ele:
            return True, mid

        if arr[mid] < ele:
            low = mid + 1
        else:
            high = mid - 1
    return False, None

binary_search(l, 3), binary_search(l, 13)

((True, 2), (False, None))

Comparison

%timeit linear_search(l, 13)

1.46 s ± 76.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit binary_search(sorted_l, 13)

4.37 μs ± 285 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%timeit binary_search(l, 13)

4.59 μs ± 795 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)