```python
from typing import List, Optional, TypeVar
T = TypeVar('T')
def binary_search(arr: List[T], target: T) -> Optional[int]:
"""
Perform binary search on a sorted list to find the index of a target element.
This function implements the binary search algorithm, which efficiently finds
a target value in a sorted array by repeatedly dividing the search interval
in half.
Args:
arr (List[T]): A sorted list of elements to search through.
target (T): The element to search for in the list.
Returns:
Optional[int]: The index of the target element if found, None otherwise.
Time Complexity:
O(log n) where n is the number of elements in the array.
Space Complexity:
O(1) - iterative implementation uses constant extra space.
Examples:
>>> binary_search([1, 2, 3, 4, 5], 3)
2
>>> binary_search([1, 2, 3, 4, 5], 6)
None
>>> binary_search(['a', 'b', 'c', 'd'], 'b')
1
>>> binary_search([], 1)
None
"""
if not arr:
return None
left: int = 0
right: int = len(arr) - 1
while left <= right:
mid: int = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return None
# Alternative recursive implementation
def binary_search_recursive(arr: List[T], target: T, left: int = 0, right: Optional[int] = None) -> Optional[int]:
"""
Perform binary search recursively on a sorted list to find the index of a target element.
Args:
arr (List[T]): A sorted list of elements to search through.
target (T): The element to search for in the list.
left (int): Left boundary of the search range (inclusive).
right (Optional[int]): Right boundary of the search range (inclusive).
Returns:
Optional[int]: The index of the target element if found, None otherwise.
Time Complexity:
O(log n) where n is the number of elements in the array.
Space Complexity:
O(log n) due to recursive call stack.
Examples:
>>> binary_search_recursive([1, 2, 3, 4, 5], 3)
2
>>> binary_search_recursive([1, 2, 3, 4, 5], 6)
None
"""
if not arr:
return None
if right is None:
right = len(arr) - 1
if left > right:
return None
mid: int = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
return binary_search_recursive(arr, target, mid + 1, right)
else:
return binary_search_recursive(arr, target, left, mid - 1)
```
This implementation provides:
1. **Main function** (`binary_search`): An iterative implementation that's more memory-efficient
2. **Alternative function** (`binary_search_recursive`): A recursive implementation for educational purposes
3. **Type hints**: Using generics (`TypeVar`) to work with any comparable type
4. **Comprehensive docstring**: Including description, parameters, return value, complexity analysis, and examples
5. **Edge case handling**: Empty lists, elements not found, etc.
6. **Clear variable names**: Self-documenting code
7. **Examples**: Doctest-style examples in the docstring
The function works with any sorted list of comparable elements (integers, strings, etc.) and returns the index of the target element if found, or `None` if not found.
