#!/usr/bin/python3
# -*- coding: utf-8 -*-
"""
Binary search implemented with recursion.
"""

from typing import List

# %% Find element in list using binary search
# During the last class before recursion,
# we covered binary search iteratively
def bin_search_rec(
    lst: List[int], item: int, low: int, high: int, indent: str = ""
) -> int:
    """
    Finds index of string in list of strings, else -1.
    Searches only the index range low to high
    Note: Upper/Lower case characters matter
    """
    print(indent, "find() range", low, high)
    range_size = (high - low) + 1
    mid = (high + low) // 2

    if item == lst[mid]:
        print(indent, "Found number.")
        pos = mid
    elif range_size == 1:
        print(indent, "Number not found.")
        pos = -1
    else:
        if item < lst[mid]:
            print(indent, "Searching lower half.")
            pos = bin_search_rec(lst, item, low, mid, indent + "    ")
        else:
            print(indent, "Searching upper half.")
            pos = bin_search_rec(lst, item, mid + 1, high, indent + "    ")

    print(indent, "Returning pos = %d." % pos)
    return pos


nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
pos = bin_search_rec(nums, 9, 0, len(nums) - 1)

if pos >= 0:
    print("\nFound at position %d." % pos)
else:
    print("\nNot found.")