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

Comments are closed.