CMPS-224 Lab 5 Algorithms with Python

Introduction

Resources: Python 3 Documentation Documentation Python Lab 5 Materials

Files Needed:

Write a program that has an list of at least 20 integers. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these values on the screen.

Function Header for Linear Search

    
        def linear_search(lst, n, x):
    
    

Psuedo Code Implementation of a Linear Search

        function linear_search(a1, a2,...,an: distinct integers, x: search_key)
            i := 1
            n := size of list
            while (i ≤ n and x != ai)
                i := i + 1
            if i ≤ n then location := i
            else location := 0
            return location{location is the subscript of the term that equals x, 
                                or is 0 if x is not found}

    

Function Header for Binary Search

    
        def binary_search(lst, x):
    
    

Call Sort on your list before you send it to the Binary Search function

    
        mylist.sort()
    
    

Psuedo Code Implementation of a Binary Search

        function binary search(a1,a2,..., an: increasing integers, x: search_key)
            i := 1 {i is the left endpoint of interval}
            j := n {j is right endpoint of interval}

            while i < j
                m := (i + j)/2 Use the floor of the value   
                if x > am then i := m + 1
                else j := m
                if x = ai then location := i
                else location := 0
                return location{location is the subscript i of the term ai equal to x, 
                                    or 0 if x is not found} 

    

What to turn in