Following is a list of unsorted/unordered numbers:

[50, 31, 21, 28, 72, 41, 73, 93, 68, 43,
45, 78, 5, 17, 97, 71, 69, 61, 88, 75,
99, 44, 55, 9]

1. Use linear search to determine the position of 1, 5, 55 and 99 in the list. Also note the number of key comparisons required to find each of these numbers in the list.
2. Use a Python function to sort/arrange the list in ascending order.
3. Again, use linear search to determine the position of 1, 5, 55 and 99 in the list and note the number of key comparisons required to find these numbers in the list.
4. Use binary search to determine the position of 1, 5, 55 and 99 in the sorted list. Record the number of iterations required in each case.

1.

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 = [50, 31, 21, 28, 72, 41, 73, 93, 68, 43, 45, 78, 5, 17, 97, 71, 69, 61, 88, 75, 99, 44, 55, 9]
keys = [1, 5, 55, 99]

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:
1 not found
5 found at index 12
Number of comparisons: 13
55 found at index 22
Number of comparisons: 23
99 found at index 20
Number of comparisons: 21

Sorted List: [5, 9, 17, 21, 28, 31, 41, 43, 44, 45, 50, 55, 61, 68, 69, 71, 72, 73, 75, 78, 88, 93, 97, 99]

Linear Search on Sorted List:
1 not found
5 found at index 0
Number of comparisons: 1
55 found at index 11
Number of comparisons: 12
99 found at index 23
Number of comparisons: 24

Binary Search on Sorted List:
1 not found
5 found at index 0
Number of comparisons: 4
55 found at index 11
Number of comparisons: 1
99 found at index 23
Number of comparisons: 5