Binary Search Implementation in Python

We all know that a Binary search is a search algorithm. The implementation code of this algorithm is everywhere. But I want to organize this on my site.

The complexity of this algorithm.

Worst Complexity: O(log n)
Average Complexity: O(log n)
Best Complexity: O(1)
Space Complexity: O(1)

Loop

def bin_search(lst, k):
	begin = 0
	end = len(lst) - 1
	index = None
	
	while begin <= end:
		mid = (begin + end) // 2
		
		if k == lst[mid]:
			index = mid
			break
		elif k > lst[mid]:
			begin = mid + 1
		elif k < lst[mid]:
			end = mid - 1
	return index
	
arr = [1, 2, 3, 5, 7, 10, 15, 20, 25]
res = bin_search(arr, 7)
print(res) # Result = 4

Recursion

def binary_search(lst, start, end, data):
	
	if start <= end:
		mid = start + (end + start) // 2
		
		if data == lst[mid]:
			return mid
		elif data > lst[mid]:
			return binary_search(lst, mid + 1, end, data)
		else:
			return binary_search(lst, start, mid - 1, data)
	else:
		return -1


lst = [2, 3, 5, 7, 9, 11, 13, 17, 19]

res = binary_search(lst, 0, len(lst) - 1, 11)
	
print(res) # 5

Tags: BinaryCode