Question

Python pls

CENGAGE MINDTAP Q Search this course Programming Exercise 11.1 x Instructions search.py + >_ Terminal + A sequential search of a sorted list can halt when the target is less than a given element in the list. 1 " 2 File: search.py 3 Project 11.1 4 5 Optimizes sequential search for sorted lists. 6 The complexity is O(n) in the worst case and 0(1) in the best case. 7 The average case is less than n / 2, because there are many lists 8 for which the search for an absent target can stop early. But the 9 average case is still approximately O(n). <> Modify the program to stop when the target becomes less than the current value being compared. In a sorted list, this would indicate that the target is not in the list and searching the remaining values is unnecessary. 10 What is the Big-O notation of the modified algorithm? Its best, worst, and average case performances? Grading When you have completed your program, click the Submit button to record your score. 11 12 def sequentialSearch(target, lyst): 13 **"Returns the position of the target item if found, 14 or -1 otherwise. 15 The lyst is assumed to be sorted in ascending order." 16 position = 0 17 while position < len(lyst): 18 if target == lyst [position]: 19 return position 20 position += 1 21 return -1 22 23 def main(): 24 ""Tests with three lists.". 25 print(sequentialSearch(3, [0, 1, 2, 3, 4])) 26 print(sequentialSearch(3, [0, 1, 2])) 27 # Should stop at second position. 28 print (sequentialSearch(3, [0, 4, 5, 6])) 29 30 if __name__ == "__main__": 31 main() 32 33 03

Answer 1

def sequentialSearch(target, lyst):
    position = 0
    while position < len(lyst):
        if target == lyst[position]:
            return position
        if target < lyst[position]:
            return -1
        position += 1

    return -1

def main():
    print(sequentialSearch(3,[0,1,2,3,4]))
    print(sequentialSearch(3,[0,1,2]))
    print(sequentialSearch(3,[0,4,5,6]))

if __name__ == "__main__":
    main()
      

#Best case = O(1)
#Average case = O(n)
#Worst case = O(n)