Searching Algorithms Linear, Binary in Python

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)
	while(first <= last):
		if(data[middle] == key):
			flag = 1
			print("key found")
		elif(data[middle]> key):
			last = middle - 1
			middle = int((first + last) /2)
			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(" ")

	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):
		print("Please enter a correct choice")

Download link


About Anuroop D

Very enthusiastic about technology and likes to share my knowledge through blogging. Has Bachelor's in Information Technology and currently pursuing my PhD in Computer Science.
This entry was posted in Python, Uncategorized and tagged , , , , , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s