Question

Design a program which uses functions to sort a list and perform a binary search. Your program should:

Iinitialize an unsorted list (using the list provided)

Display the unsorted list

Sort the list

Display the sorted list.

Set up a loop to ask the user for a name, perform a binary search, and then report if the name is in the list. Use a sentinel value to end the loop.

Do not use the Python built in sort function to sort the list, instead write one or more functions to implement either the bubble sort or insertion sort (you choose the one you want to implement). The algorithms for the bubble sort and insertion sort are provided in the Word document attachment.

Implement the binary search algorithm as a function. Algorithms are provided in the Word document attachment for an iterative version or recursive version of the binary search. You choose the one you want to implement.

Use this test list: [ 'Paul', 'Aaron', 'Jacob', 'James', 'Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill' ]

Turn in your source code with IPO comments at the top of the file

A screen shot showing the results of your testing.

Answer 1

def binarySearch(arr, lower, upper, target):
    if upper >= lower:
        mid = lower + ((upper - lower) // 2)
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            return binarySearch(arr, lower, mid - 1, target)
        else:
            return binarySearch(arr, mid + 1, upper, target)
    return -1


def bubbleSort(list):
    needNextPass = True
    k = 1
    while k < len(list) and needNextPass:
        # List may be sorted and next pass not needed
        needNextPass = False
        for i in range(len(list) - k):
            if list[i] > list[i + 1]:
                # swap list[i] with list[i + 1]
                temp = list[i]
                list[i] = list[i + 1]
                list[i + 1] = temp
                needNextPass = True  # Next pass still needed

# A test method
def main():
    list = [ 'Paul', 'Aaron', 'Jacob', 'James', 'Bill', 'Sara', 'Cathy', 'Barbara', 'Amy', 'Jill' ]
    bubbleSort(list)
    print("Sorted list: ")
    for v in list:
        print(v, end="\t")
    print()

    index = binarySearch(list,0,len(list)-1,'Bill')
    if(index == -1):
        print("Targer not found")
    else:
        print("Target found at index",index)

main()