binary_search.py

import time


def binary_search_rec(nums, target, low, high, comparisons):
    """Recursive binary search helper — returns (index, comparisons)."""
    if low > high:
        return -1, comparisons

    mid = low + ((high - low) // 2)
    comparisons += 1

    if nums[mid] == target:
        return mid, comparisons
    elif target < nums[mid]:
        return binary_search_rec(nums, target, low, mid - 1, comparisons)
    else:
        return binary_search_rec(nums, target, mid + 1, high, comparisons)


def binary_search(nums, target):
    """
    Binary Search: divide and conquer on a sorted array.
    Time: O(log n) | Space: O(log n) recursive stack
    Requires sorted input — sorts internally.
    """
    arr_sort = sorted(nums)

    t_start = time.perf_counter()
    result, comparisons = binary_search_rec(arr_sort, target, 0, len(arr_sort) - 1, 0)
    t_stop = time.perf_counter()

    elapsed = t_stop - t_start
    return (result, arr_sort, elapsed, comparisons)