Search_bisection_recursion

# 4.8 (102)  Search_bisection_recursion Pythom code by Ken Adams
# Finding a number from a sorted list by bisection and recursion
# test data all these items on a list  [7, 11, 25, 31, 43, 53, 64, 71, 85, 92]
# additional test data these items not on the list 3,8,18,27,41,51,60,68,75,89 was used to verify no item present
# In above we choose a less than the bottom of the list, a number more han the top of the list, and numbers between
# any two numbers on the list

#PICK YOUR TEST DATA
my_this = [7, 11, 25, 31, 43, 53, 64, 71, 85, 92]# used for testing
#my_this = [7, 11, 25, 25, 25, 25, 64, 71, 85, 92]# used to test finding the lowest index of a number in the list
#my_this = [25, 25, 25, 25, 25, 25, 64, 71, 85, 92]# same as above
print(my_list)

my_number = 25 # set the number to search for

# note: we need four parameters
def search(lower, upper, S_list, num):# this is the basic bisection algorithm
    print("lower " + str(lower) + " upper " +str(upper)) # lower and upper are indexes in the list
    mid = (lower+upper)//2 # roughly the mid point
    if mid == lower: # This is the test that stops recursion, whe mid = lower there can be no more bisections
        if S_list[mid] == num: # first check if mid is the correct answer
            return mid
        else:
            print(" number not on list ")# if mid is not the answer then the number is not on the list
            return None
    # At this point we have decided that there is at least one more recursion
    if S_list[mid] == num: # if mid correct then return it
       return mid
    if S_list[mid] > num: # we do another recursion on the lower part of the list
        return search(lower, mid, S_list, num)
    if S_list[mid] < num: # we do another recursion on the upper part of the list
        return search(mid, upper, S_list, num)
    # all posibilities have been exausted

# this little function lets us get away with two parameters
def run_search(my_list, my_number):
    return search(0,len(my_list), my_list, my_number)
# thats all folks

# this function, if it finds the requird number, will return the lowest index where it appears
def run_search_smallest(my_list, my_number):
    first = search(0,len(my_list), my_list, my_number)# get one place to start
    while my_list[first] == my_number and first >= 0:
        store_first = first #store the result of the last loop throught the while
        first  -= 1 # decrement first
    return store_first
    # note: the last time through the loop first has already been decremented so is one index too small
    # but store_first holds the answer we want
    # should store_first = 0, then first is decremented to -1,
    # the 'and' part of the while logic prevents this causing trouble

#CHOOSE WHAT FUNCTION TO RUN
#position = search(0,len(my_list), this_list, my_number)# works with four parameters
position = run_search(this_list, my_number)# works with two parameters
position = run_search_smallest(this_list, my_number)# find the first correct index

# prints results
print(str(my_number) + " is at position " + str(position))


print("bye from Ken")