# ======================================================================
# binary-search.py
# Scott F. H. Kaplan -- sfkaplan@cs.amherst.edu
# 2014 October

# A collection of implementations of the binary search algorithm on
# lists of randomly selected integers.
# ======================================================================



# ======================================================================
# IMPORTS

import random
# ======================================================================



# ======================================================================
# Use a loop to repeatedly halve the range of positions in the given
# list l within which the value v could possibly be found.

def iterativeBinarySearch (l, v):

    # Begin by setting the range to cover the entire list.
    lo = 0
    hi = len(l) - 1

    # Repeat until the value is found (which will trigger a return
    # from inside the loop) or until there is no range left to check
    # (lo and hi cross).
    while lo <= hi:
        mid = (lo + hi) // 2
        if l[mid] == v:
            return mid
        elif l[mid] < v:
            lo = mid + 1
        else: # l[mid] > v
            hi = mid - 1
# ======================================================================



# ======================================================================
# Recursively divide the given list l in half in a search for the
# value v.

def slicingRecursiveBinarySearch (l, v):

    # Base case: An empty list cannot contain v.
    if len(l) == 0:
        return None

    # Recursive case: Test the middle element.  If needed, search the
    # remaining relevant half for v.
    mid = len(l) // 2
    if l[mid] == v:
        return mid
    elif l[mid] > v:
        return slicingRecursiveBinarySearch(l[:mid], v)
    else: # l[mid] < v
        # The tricky step: If we search the upper half of l, then the
        # result is "off" by mid+1, so we need to add that value back
        # into the result.
        i = slicingRecursiveBinarySearch(l[mid + 1:], v)
        if i == None:
            return None
        else:
            return i + mid + 1
# ======================================================================



# ======================================================================
# A combination of the two previous approaches.  Search recursively,
# but by repeatedly reducing the range of potential indices within
# which v might be found.

# A "stub function" whose only job is to call the function that truly
# does the work, but with additional arguments to set the initial
# range of indices to examine.
def indexingRecursiveBinarySearch (l, v):
    return doIndexingRecursiveBinarySearch(l, v, 0, len(l) - 1)

# The real recursive function that looks for v within l, but only
# within the range of indices between lo and hi (inclusive).
def doIndexingRecursiveBinarySearch (l, v, lo, hi):
    if lo <= hi:
        mid = (lo + hi) // 2
        if l[mid] == v:
            return mid
        elif l[mid] > v:
            return doIndexingRecursiveBinarySearch(l, v, lo, mid - 1)
        else: # l[mid] < v
            return doIndexingRecursiveBinarySearch(l, v, mid + 1, hi)
# ======================================================================



# ======================================================================
def makeRandomList (n):
    l = [random.randrange(0, n) for _ in range(n)]
    l.sort()
    return l
# ======================================================================



# ======================================================================
def showResults (l, v, i):
    if i == None:
        print('Not found')
    else:
        print('i = {0}, v = {1}, l[i] = {2}'.format(i, v, l[i]))
# ======================================================================



# ======================================================================
# Drive the demonstration.  After asking the user for a list length to
# process, create the list and then search it for a randomly chosen
# value using all of the search variants.

def main ():
    n = int(input('List length: '))
    l = makeRandomList(n)
    v = random.randrange(0, n)
    p = iterativeBinarySearch(l, v)
    showResults(l, v, p)
    q = slicingRecursiveBinarySearch(l, v)
    showResults(l, v, q)
    r = indexingRecursiveBinarySearch(l, v)
    showResults(l, v, r)
# ======================================================================



# ======================================================================
# Call main to start things off...

main()
# ======================================================================