Binary Search

Moves through the list until the wanted item is found using divide and conquer.

Implementation

from random import randint, choice
data = [randint(1, 100) for x in range(10)]
data.sort()
 
# implementation
def binary_search(arr: list[int], target: int) -> int:
	lower_bound = 0
	upper_bound = len(arr) - 1
	while lower_bound <= upper_bound:
		mid_point = lower_bound + (upper_bound - lower_bound) // 2
		if arr[mid_point] == target:
			return mid_point
		elif arr[mid_point] < target:
			lower_bound = mid_point + 1
		else:
			upper_bound = mid_point - 1
 
print(binary_search(data, choice(data)))

Advantages

• Fast on larger datasets
• O(1) best case scenario, O(log n) worst case scenario
• O(1) space

Disadvantages

• Harder to program in comparison to Linear Search
• Negligible speed benefits on small datasets