Question

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]

• 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.
• Use a Python function to sort/arrange the list in ascending order.
• 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.
• 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.

Answer 1

According to the Linear Search algorithm the position and number of comparisons for the elements are given as:

1: not found in the array and the number of comparisons is 24.

5: position = 13, number of comparisons is 13.

55: position = 23, number of comparisons are 23.

99: position = 21, number of comparisons are 21.

After sorting,

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]

1: not found in the array and the number of comparisons is 24.

5: position = 1, number of comparisons is 1.

55: position = 12, number of comparisons are 12.

99: position = 24, number of comparisons are 24.

By applying Binary Search:

1: not found in the array

5: position = 1

55: position = 12

99: position = 24