Binary search algorithm use cases

binary_search.py

import random
import timeit
from typing import List, Optional
import unittest

# simple binary search algrothim. requires a sorted list function
def binary_search(sorted_list: List[str], target: str) -> Optional[int]:
    left, right = 0, len(sorted_list) - 1

    while left <= right:
        mid = (left + right) // 2

        if sorted_list[mid] == target:
            return mid
        elif sorted_list[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return None
  
 # auto complete function using binary search for a sorted list of strings
def autocomplete(sorted_list: List[str], target: str) -> Optional[str]:
    start_index = None

    # Binary search for the target
    left, right = 0, len(sorted_list) - 1
    while left <= right:
        mid = (left + right) // 2
        if sorted_list[mid].startswith(target):
            return sorted_list[mid]
        elif sorted_list[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # If target not found, search for the next string that starts with the target
    if start_index is not None:
        for i in range(start_index, len(sorted_list)):
            if sorted_list[i].startswith(target):
                return sorted_list[i]

    return None
  
# find the closest match to a target in a sorted list function using binary search
def closest_match(sorted_list: List[int], target: int) -> Optional[int]:
    closest = None
    left, right = 0, len(sorted_list) - 1

    while left <= right:
        mid = (left + right) // 2

        if sorted_list[mid] == target:
            return sorted_list[mid]
        elif sorted_list[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

        if closest is None or abs(sorted_list[mid] - target) < abs(closest - target):
            closest = sorted_list[mid]

    return closest
  
# range search function using binary search
def range_search(sorted_list: List[int], start_range: int, end_range: int) -> Optional[int]:
    left, right = 0, len(sorted_list) - 1

    while left <= right:
        mid = (left + right) // 2

        if sorted_list[mid] >= start_range and sorted_list[mid] <= end_range:
            return mid
        elif sorted_list[mid] < start_range:
            left = mid + 1
        else:
            right = mid - 1
            
    return None
  
# binary search function with start index
def binary_search_start_index(arr: List[int], target[int], start_index = 0) -> Optional[int]:
    # get left and right values from array
    left, right = start_index, len(arr) - 1

    # binary search
    while left <= right:
        # get middle value
        mid = (left + right) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1
    
# Basic Binary Search
# test 1: search for 3 in a sorted list of 10 integers
sorted_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 3
# print time taken to run the function
print('Binary Search:')
print('Test 1:')
print('Target in list:')
print(binary_search(sorted_list, target))
print(timeit.timeit(lambda: binary_search(sorted_list, target), number=10000))
print('')

# test 2: search for a random integer in a sorted list of 1 million integers and a random integer not in the list
sorted_list = sorted(random.sample(range(10000000), 1000000))

# generate random targets
target_in_list = random.choice(sorted_list)
target_not_in_list = random.randint(10000000, 20000000)

# print time taken to run the function for both targets
print('Test 2:')
print('Target in list:')
print(binary_search(sorted_list, target_in_list))
print(timeit.timeit(lambda: binary_search(sorted_list, target_in_list), number=10000, globals=globals()))
print('Target not in list:')
print(binary_search(sorted_list, target_not_in_list))
print(timeit.timeit(lambda: binary_search(sorted_list, target_not_in_list), number=10000, globals=globals()))
print('')

# Auto Complete with Binary Search
# test 1: search for 'a' in a sorted list of words
# generate a sorted list of words
words = ['apple', 'banana', 'cherry', 'date', 'elderberry', 'fig', 'grape', 'honeydew', 'kiwi', 'lemon']
sorted_words = sorted(words)
# print time taken to run the function
print('Auto Complete:')
print('Test 1:')
print('Target in list:')
print(autocomplete(sorted_words, 'a'))
print(timeit.timeit(lambda: autocomplete(sorted_words, 'a'), number=10000, globals=globals()))
print('')

# Find Clsest Match with Binary Search
# test 1: Finding the closest match to an integer in a sorted list
# generate a sorted list of 100 random integers
sorted_list = sorted(random.sample(range(1000), 100))
# generate a random target
target = random.randint(0, 1000)
print('Closest Match:')
print('Test 1:')
print('Target in list:')
print(closest_match(sorted_list, target))
print(timeit.timeit(lambda: closest_match(sorted_list, target), number=10000, globals=globals()))
print('')

# Range Search
# test 1: Finding the range of a sorted list
# generate a sorted list of 100 random integers
sorted_list = sorted(random.sample(range(1000), 100))
# rages
start_range = 300
end_range = 600

print('Range Search:')
print('Test 1:')
print('Target in list:')
print(range_search(sorted_list, start_range, end_range))
print(timeit.timeit(lambda: range_search(sorted_list, start_range, end_range), number=10000, globals=globals()))
print('')

# Binary Search with Start Index
# test 1: Find item in list
# Generate 10 length arr and define target
arr = [i + 1 for i in range(10)]
target = 3

print('Binary Searchwith Start Index:')
print('Test 1:')
print('Target in list:')
print(binary_search_start_index(arr, target)) # expected 2
print(timeit.timeit(lambda: binary_search_start_index(arr, target), number=10000, globals=globals()))
print('')

print('Test 2:')
print('Target not in list:')
print(binary_search_start_index(arr, target, 3)) # expected -1
print(timeit.timeit(lambda: binary_search_start_index(arr, target, 3), number=10000, globals=globals()))
print('')