Python program for Binary Search in linear list

In this post,we are going to write python program for binary search in linear list. Binary search in one of the popular search techniques in data structure. We can implement binary search technique in python to search given item or element in minimum possible comparison.

In Binary search, array is to be created to store list of elements. This array must be scanned and sorted in any order . It means that array must be sorted in ascending order. if array element is not be in sorted order then we need to use sorting technique to sort the array element first and only then we can use binary search technique to search the element in list.

In binary search , array is divided into segments. Middle element is first find out and then search element is compared with middle element of array.If search element is more than middle element,latter part of array becomes new array segment to be scanned.

If search element is less than middle element,former part of array becomes new array segment to be scanned. The Same process is repeated for new segment until either search element is found.

Note that ,binary search can work for sorted arrays only

Python program for binary search in linear list

def binary_search(item_list,item):
	first = 0
	last = len(item_list)-1
	while( first<=last):
		mid = (first + last)//2
		if item_list[mid] == item :
			return mid
		else:
			if item < item_list[mid]:
				last = mid - 1
			else:
				first = mid + 1	
	return False

n = int(input("Enter linear list size :"))
print("Enter elements for linear list in ascending order :")

#initialize list of size n with zeros
item_list = [0]*n

# storing elements in linear list one by one
for i in range(n) :
    item_list[i] = int(input("Element  " + str(i)+" :"))

# Looking for element in linear list
item = int(input("Enter element to be searched for :"))
# calling function binary_search
index = binary_search(item_list,item)

# if search element present in list then it display index and position of it
# otherwise it display error message
if index :
    print("Element found at index :",index,"position :",(index+1))
else :
    print("Given element could not be found.\n")

Output:

Enter linear list size :10
Enter elements for linear list in ascending order :
Element  0 :11
Element  1 :22
Element  2 :33
Element  3 :44
Element  4 :55
Element  5 :66
Element  6 :77
Element  7 :88
Element  8 :99
Element  9 :100
Enter element to be searched for :77
Element found at index : 6 position : 7