Binary Search
- divide and conquer algorithm that finds a target value in a sorted list
How it works:
- sorts the list first
- splits the area that needs to be searched in half each time, eliminates the half that the target value is not in
benefits: cuts time it takes to search an array, makes it much faster
Python implementation
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2 # Find middle index
if arr[mid] == target:
return mid # Target found
elif arr[mid] < target:
low = mid + 1 # Search right half
else:
high = mid - 1 # Search left half
return -1 # Target not found </code> # Example usage:
numbers = [1, 3, 5, 7, 9, 11, 13]
print(binary_search(numbers, 7)) # Output: 3
cases to consider empty lists returns -1 one element in a list only works if the target matches if the targets are not in the list then it returns -1
Big O Notation
- describes the worst-case performance of an algorithm of input size n
Practical Applications
- Database and indexing, searching in sorted records
- AI pathfinding, finding best moves or decisions
- Search Algorithms in Libraries
Binary Search with Strings
- strings must be sorted alphabetically and capital letters should come before lowercase