Binary Search

Last updated Aug 6, 2023 Edit Source

• Programming
• Interviewprep
• Algorithms

El algoritmo consiste en saltar entre la estructura partiendola en la mitad cada vez hasta encontrar el elemento. Para esto, se requiere que la estructura este ordenada.

Debido a los saltos a la mitad de la estructura, el notes/Big O de este algoritmo es O(log n).

Es uno de los algoritmos mas clasicos y una de las bases para otros algoritmos puesto que es el primer algoritmo que requiere que la estructura de datos este ordenada.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

def binary_search(v, arr):
	start = 0
	end = len(arr)

	while start < end:
		mid = start + (end - start) / 2
		val = arr[mid]
		if val == v:
			return True
		elif val > v:
			end = mid
		else:
			start = mid + 1