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)
	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")

Output:
search
Download link

Advertisements

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 Master's 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:

WordPress.com Logo

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

Google+ photo

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

Twitter picture

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

Facebook photo

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

Connecting to %s