Following is a list of unsorted/unordered numbers: Use linear search to determine the position of 1, 5, 55

Q. 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 :-

def linearSearch(list, key):
    found = 0
    for index in range(0,len(list)):
        if list[index] == key:
            return key ,"is at index :-", index+1 , "and number of key  comparisons required", index
    if found == 0 :
        return key ,"is not found !!"

def bisearch (ar, key):
    it = 0
    low = 0
    high = len(ar)-1
    while low <= high :
        it += 1
        mid = int ((low+high)/2)
        if key == ar[mid]:
            return key ,"is at index :-", mid , "Number  of  iterations required :-", it
        elif key < ar [mid]:
            high = mid - 1
        else :
            low = mid +1
    else :
        return key ,"is not found !!"

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

#i
print( linearSearch (lst , 1))
print(linearSearch (lst , 5))
print(linearSearch (lst , 55 ))
print( linearSearch (lst , 99 ))

#ii
lst.sort()

#iii
print( linearSearch (lst , 1))
print( linearSearch (lst , 5))
print( linearSearch (lst , 55 ))
print( linearSearch (lst , 99 ))

#iv
print( bisearch (lst , 1))
print( bisearch (lst , 5))
print( bisearch (lst , 55 ))
print( bisearch (lst , 99 ))

Output:-

(1, 'is not found!!')
(5, 'is at index :-', 13, 'and number of key  comparisons required', 12)
(55, 'is at index :-', 23, 'and number of key  comparisons required', 22)
(99, 'is at index :-', 21, 'and number of key  comparisons required', 20)
(1, 'is not found !!')
(5, 'is at index :-', 1, 'and number of key  comparisons required', 0)
(55, 'is at index :-', 12, 'and number of key  comparisons required', 11)
(99, 'is at index :-', 24, 'and number of key  comparisons required', 23)
(1, 'is not found !!')
(5, 'is at index :-', 0, 'Number  of  iterations required :-', 4)
(55, 'is at index :-', 11, 'Number  of  iterations required :-', 1)
(99, 'is at index :-', 23, 'Number  of  iterations required :-', 5)
>>>