# 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```
Scroll to Top