Two of the basic search algorithms are Linear search and Binary search. Linear search is very straight in it’s implementation. On the other hand, binary search is something which tries to reduce the time complexity of searching for any give amount of data.
Time complexity of Linear, Binary searches are in worst case scenario: O(n), O(logn) respectively.
The implementation of Linear search is as follows: check the key with each and every element from the starting of the data. If the lenght of the give data is n and key matches with the last element of the data, then it will take n iterations to search for the key. Hence the complexity of O(n).
In case of binary search, sort the give data either in increasing order or decreasing order. Check if middle element matches the key then key is found, Else check if middle element is greater than key then we need not to search for the half of data which is greater than key, hence move the last to middle -1. If middle element is less than key then move first to middle + 1.
The following code has menu which have options for both Linear search, Binary search.
def lsearch(data, key): flag = 0 for i in range(0, len(data)): if data[i] == key: flag = 1 print("Key found at position:", i) if(flag == 0): print("Key not found in the give list") def bsearch(data, key): flag = 0 first = 0 last = len(data) - 1 middle = int((first + last) / 2) sort(data) while(first <= last): if(data[middle] == key): flag = 1 print("key found") break; elif(data[middle]> key): last = middle - 1 middle = int((first + last) /2) else: first = middle + 1 middle = int((first + last) /2) if(flag == 0): print("Key not found in the give list") def sort(data): for i in range(0, len(data)): for j in range(i+1, len(data)): if(data[i] > data[j]): data[i], data[j] = data[j],data[i] data = input("Enter data separated by spaces:").split(" ") while(True): print("\n1. Linear Search\n2. Binary Search\n3. Exit"); choice = int(input("\nEnter your choice from above menu:")) if(choice == 1): key = input("Enter the key to be searched:") lsearch(data, key) elif(choice == 2): key = input("Enter the key to be searched:") bsearch(data, key) elif(choice == 3): break; else: print("Please enter a correct choice")