Pesquisa binária Python
Harshit Jindal
30 janeiro 2023
Python
Python Algorithm
Algoritmo de pesquisa binária
Vamos supor que temos um array não classificado A[] contendo n elementos, e queremos encontrar um elemento X.
-
Defina
locomo0ehicomon - 1. -
Enquanto
lo<hi, definamid=lo + (hi - lo)/2.- Se
A[mid]==X, encontramos o elemento que retorna o índicemid. - Se
A[mid]<X, descarte a metade esquerda dos elementos e definalocomomid+1. - Caso contrário, se
A[mid]>X, descarte a metade direita dos elementos e definahicomomid-1.
- Se
-
Elemento não encontrado, então retorne
-1.
Programa Python para pesquisa binária
def binary_search(arr, x, n):
lo = 0
hi = n - 1
mid = 0
while lo <= hi:
mid = (hi + lo) // 2
if arr[mid] < x:
lo = mid + 1
elif arr[mid] > x:
hi = mid - 1
else:
return mid
return -1
arr = [2, 3, 4, 1, 5]
x = 4
n = len(arr)
result = binary_search(arr, x, n)
if result == -1:
print("Element not found")
else:
print("Element is present at index", str(result))
Resultado:
Element is present at index 2
Está gostando dos nossos tutoriais? Inscreva-se no DelftStack no YouTube para nos apoiar na criação de mais vídeos tutoriais de alta qualidade. Inscrever-se
Autor: Harshit Jindal
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn