Log n time complexity

binary_search.py

from typing import Any, List


def binary_search(list_: List[int], target_value: int) -> int:
    """
    Perform a binary search of a sorted input list for a target value. 
    Return the index of the target value in the list, or -1 if not found.
    """
    # Initialize left and right indexes for start of search
    left = 0
    right = len(list_) - 1

    # Perform binary search
    while left <= right:

        # Calculate the middle index of the remaining list values to be searched
        middle = left + (right - left) // 2

        # Check if target_value is at the middle index. If so, we've found it and we're done.
        if list_[middle] == target_value:
            return middle

        # If target_value is greater than the middle value, ignore the left half of the remaining list values
        elif list_[middle] < target_value:
            left = middle + 1

        # If target_value is less than the middle value, ignore right half of the remaining list values
        else:
            right = middle - 1

    # Return a sentinel value of -1 if the target_value was not found in the whole list
    return -1