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].

1. Use linear search to find the position of Amazing, Perfect, Great and Wondrous in the list. Also note the number of key comparisons required to find these words in the list.
2. Use a Python function to sort the list.
3. Again, use linear search to determine the position of Amazing, Perfect, Great and Wondrous in the list and note the number of key comparisons required to find these words in the list.
4. Use binary search to determine the position of Amazing, Perfect, Great and Wondrous in the sorted list. Record the number of iterations required in each case.

def linear_search(arr, key):
    comparisons = 0  
    for k in range(len(arr)):
        comparisons += 1  
        if key == arr[k]:
            return k, comparisons  
    return -1, comparisons  

def binary_search(arr, key):
    comparisons = 0
    first = 0
    last = len(arr) - 1
    
    while first <= last:
        mid = (first + last) // 2
        comparisons += 1
        
        if arr[mid] == key:
            return mid, comparisons
        elif key < arr[mid]:
            last = mid - 1
        else:
            first = mid + 1
    
    return -1, comparisons


original_list = ['Perfect', 'Stupendous', 'Wondrous',
'Gorgeous', 'Awesome', 'Mirthful', 'Fabulous', 'Splendid',
'Incredible', 'Outstanding', 'Propitious', 'Remarkable',
'Stellar', 'Unbelievable', 'Super', 'Amazing']

keys = ['Amazing', 'Perfect', 'Great', 'Wondrous']

print("Linear Search on Unsorted List:")
for key in keys:
    pos, comparisons = linear_search(original_list, key)
    if pos == -1:
        print(key, "not found")
    else:
        print(key, "found at index", pos)
        print("Number of comparisons:", comparisons)

original_list.sort()
print("\nSorted List:", original_list)


print("\nLinear Search on Sorted List:")
for key in keys:
    pos, comparisons = linear_search(original_list, key)
    if pos == -1:
        print(key, "not found")
    else:
        print(key, "found at index", pos)
        print("Number of comparisons:", comparisons)

print("\nBinary Search on Sorted List:")
for key in keys:
    pos, comparisons = binary_search(original_list, key)
    if pos == -1:
        print(key, "not found")
    else:
        print(key, "found at index", pos)
        print("Number of comparisons:", comparisons)

Output

Linear Search on Unsorted List:
Amazing found at index 15
Number of comparisons: 16
Perfect found at index 0
Number of comparisons: 1
Great not found
Wondrous found at index 2
Number of comparisons: 3

Sorted List: ['Amazing', 'Awesome', 'Fabulous', 'Gorgeous', 'Incredible', 'Mirthful', 'Outstanding', 'Perfect', 'Propitious', 'Remarkable', 'Splendid', 'Stellar', 'Stupendous', 'Super', 'Unbelievable', 'Wondrous']

Linear Search on Sorted List:
Amazing found at index 0
Number of comparisons: 1
Perfect found at index 7
Number of comparisons: 8
Great not found
Wondrous found at index 15
Number of comparisons: 16

Binary Search on Sorted List:
Amazing found at index 0
Number of comparisons: 4
Perfect found at index 7
Number of comparisons: 1
Great not found
Wondrous found at index 15
Number of comparisons: 5