Question

Write a program that takes as input the following unsorted list of English words: [Perfect, Stupendous, Wondrous, Gorgeous, Awesome, Mirthful, Fabulous, Splendid, Incredible, Outstanding, Propitious, Remarkable, Stellar, Unbelievable, Super, Amazing].

Accepted Answer

Program to demonstrate Linear and Binary Search on a list of words def linear search(arr, key): comparisons = 0 for i in range(len(arr)): comparisons += 1 if arr[i] == key: return i, comparisons return -1, comparisons def binary search(arr, key): low = 0 high = len(arr) - 1 iterations = 0 while low <= high: iterations += 1 mid = (low + high) // 2 if arr[mid] == key: return mid, iterations elif arr[mid] < key: low = mid + 1 else: high = mid - 1 return -1, iterations Unsorted list words = ['Perfect', 'Stupendous', 'Wondrous', 'Gorgeous', 'Awesome', 'Mirthful', 'Fabulous', 'Splendid', 'Incredible', 'Outstanding', 'Propitious', 'Remarkable', 'Stellar', 'Unbelievable', 'Super', 'Amazing'] search keys = ['Amazing', 'Perfect', 'Great', 'Wondrous'] (a) Linear Search on Unsorted List print("(a) Linear Search on Unsorted List:") for key in search keys: pos, comp = linear search(words, key) if pos != -1: print(f"key: Position = pos, Comparisons = comp") else: print(f"key: Not found, Comparisons = comp") (b) Sort the list words.sort() print(" (b) Sorted List:") print(words) (c) Linear Search on Sorted List print(" (c) Linear Search on Sorted List:") for key in search keys: pos, comp = linear search(words, key) if pos != -1: print(f"key: Position = pos, Comparisons = comp") else: print(f"key: Not found, Comparisons = comp") (d) Binary Search on Sorted List print(" (d) Binary Search on Sorted List:") for key in search keys: pos, iters = binary search(words, key) if pos != -1:…

Explanation

Apar Academy