Skip to content

Instantly share code, notes, and snippets.

@alexsc6955

alexsc6955/binary_search.py

Created June 5, 2023 22:32
Show Gist options
  • Save alexsc6955/ef37d9d809dbdd5138018bbf6257e89a to your computer and use it in GitHub Desktop.
Save alexsc6955/ef37d9d809dbdd5138018bbf6257e89a to your computer and use it in GitHub Desktop.
Download ZIP
Binary search algorithm use cases
Raw
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('')
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment