🔎 Binary Search

Search Problem §

Find the index of element in a sorted array if it exists or the insertion point if it doesn’t.

Theory §

Recursively divide the array into two halves; must appear in only one of these two halves, depending on whether it’s greater or less than the midpoint between the halves.

Implementation §

def binary_search(arr, x):
	lo, hi = 0, len(arr) - 1
	while lo <= hi:
		mid = int((lo + hi) / 2)
		if arr[mid] == x:
			return mid
		lo = mid + 1 if x > arr[mid] else lo
		hi = mid - 1 if x < arr[mid] else hi
	return lo

Runtime §

Binary search divides the array of size into two, so it has the runtime recurrence . Therefore, our runtime is .