import typing

def sortedSearchPrime(lst: list, needle: typing.Any, lb: int, ub: int) -> int:
    """
    Returns the index of needle in lst, between lb and ub. lst must be sorted.
    Returns -1 if needle isn't found.
    """
    print(lst[lb:ub])
    if lb == ub: # lst == []
        return -1
    elif ub == lb + 1 and lst[lb] == needle:
        return lb
    midpoint = (ub - lb) // 2 + lb
    if lst[midpoint] == needle:
        return sortedSearchPrime(lst, needle, lb, midpoint+1)
    elif lst[midpoint] < needle:
        return sortedSearchPrime(lst, needle, midpoint+1, ub)
    else: # lst[midpoint] > needle
        return sortedSearchPrime(lst, needle, lb, midpoint)
    
def sortedSearch(lst: list, needle: typing.Any) -> int:
    return sortedSearchPrime(lst, needle, 0, len(lst))
    
x = sorted([2, 4, 6, 0, 1, 8, 6, 5, 3, 0, 9])
print(x)
print(sortedSearch(x, 6))

[0, 0, 1, 2, 3, 4, 5, 6, 6, 8, 9]
[0, 0, 1, 2, 3, 4, 5, 6, 6, 8, 9]
FOO
[5, 6, 6, 8, 9]
BAR
[5, 6, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR
[5, 6]
BAR

---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
Input In [3], in <cell line: 28>()
     26 x = sorted([2, 4, 6, 0, 1, 8, 6, 5, 3, 0, 9])
     27 print(x)
---> 28 print(sortedSearch(x, 6))

Input In [3], in sortedSearch(lst, needle)
     23 def sortedSearch(lst: list, needle: typing.Any) -> int:
---> 24     return sortedSearchPrime(lst, needle, 0, len(lst))

Input In [3], in sortedSearchPrime(lst, needle, lb, ub)
     17 elif lst[midpoint] < needle:
     18     print("FOO")
---> 19     return sortedSearchPrime(lst, needle, midpoint+1, ub)
     20 else: # lst[midpoint] > needle
     21     return sortedSearchPrime(lst, needle, lb, midpoint)

Input In [3], in sortedSearchPrime(lst, needle, lb, ub)
     14 if lst[midpoint] == needle:
     15     print("BAR")
---> 16     return sortedSearchPrime(lst, needle, lb, midpoint+1)
     17 elif lst[midpoint] < needle:
     18     print("FOO")

Input In [3], in sortedSearchPrime(lst, needle, lb, ub)
     14 if lst[midpoint] == needle:
     15     print("BAR")
---> 16     return sortedSearchPrime(lst, needle, lb, midpoint+1)
     17 elif lst[midpoint] < needle:
     18     print("FOO")

    [... skipping similar frames: sortedSearchPrime at line 16 (23 times)]

Input In [3], in sortedSearchPrime(lst, needle, lb, ub)
     14 if lst[midpoint] == needle:
     15     print("BAR")
---> 16     return sortedSearchPrime(lst, needle, lb, midpoint+1)
     17 elif lst[midpoint] < needle:
     18     print("FOO")

Input In [3], in sortedSearchPrime(lst, needle, lb, ub)
     13 midpoint = (ub - lb) // 2 + lb
     14 if lst[midpoint] == needle:
---> 15     print("BAR")
     16     return sortedSearchPrime(lst, needle, lb, midpoint+1)
     17 elif lst[midpoint] < needle:

File /mnt/zfs/jupyter-p03/home/gkrichar/.ipython/profile_default/startup/cs114-setup.py:5, in print(*args, **kwargs)
----> 5 def print(*args, **kwargs): builtins.print(*args, **kwargs); sys.stdout.flush(); time.sleep(0.04)

KeyboardInterrupt: