Recursive and iterative versions of the binary search algorithm.

binary_search.py

from typing import Union, TypeVar

E = TypeVar("E", bound=Union[int, float])


def recursive_binary_search(array: list[E], left: E, right: E, target: E) -> int:
    if array != sorted(array):
       array.sort()
    if left is None:
        left = 0
    if right is None:
        right = len(array) - 1
    if left > right:  # type: ignore
        return -1

    mid_point: int = left + abs(left - right) // 2  # type: ignore
    if target == array[mid_point]:
        return mid_point
    if target < array[mid_point]:  # type: ignore
        return recursive_binary_search(array, left, mid_point - 1, target)
    return recursive_binary_search(array, mid_point + 1, right, target)


def iterative_binary_search(array: list[E], target: E) -> int:
    array.sort()
    left: int = 0
    right: int = len(array) - 1
    while left <= right:
        mid_point: int = left + abs(left - right) // 2
        if target == array[mid_point]:
            return mid_point
        if target < array[mid_point]:  # type: ignore
            right = mid_point - 1
        else:
            left = mid_point + 1

    return -1


assert iterative_binary_search(
    array=[26, 3, 1, 8.0, 5, 34, 1, 12.5], target=1
) == recursive_binary_search(
    array=[26, 3, 1, 8.0, 5, 34, 1, 12.5], left=0, right=None, target=1
)  # type: ignore