Binary Search Algorithm

Binary Search.py

#!/usr/bin/env python3

def binary_search(array, left, right, key):
	mid = left + ((right - left) // 2)  # finds the midpoint between left and right

	if array[mid] == key:
		return mid  # returns the index if the key is found

	elif key < array[mid]:
		return binary_search(array, left, mid-1, key) # binary searches the left portion

	elif key > array[mid]:
		return binary_search(array, mid, right, key)  # binary searches the right portion

	else:
		return -1

print("Enter the elements of the array")
a = [int(n) for n in input().split()] # takes the array input

if a != a.sort(): # checks whether array is sorted
	a.sort()  # if unsorted sorts the array
	print("The array is unsorted")
	print("The sorted array is...")
	print(a)  # prints new sorted array
else:
	print("The array is already sorted")
	print("The input array is...")
	print(a)  # prints old sorted array

print("Enter the value to be searched for")
key = int(input())  # asks for value to be binary searched

l = 0
r = len(a) - 1

ans = binary_search(a, l, r, key)

if ans == -1:
	print("Value not found")
else:
	print("Value found at index " + str(ans))