Pesquisa binária Python
Harshit Jindal
30 janeiro 2023
![Pesquisa binária Python](/img/Python/ag-feature-image---python-binary-search.webp)
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
lo
como0
ehi
comon - 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 definalo
comomid+1
. - Caso contrário, se
A[mid]
>X
, descarte a metade direita dos elementos e definahi
comomid-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
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