Pesquisa binária Python

  2. HowTo
  3. Como-Fazer de Python
  4. Pesquisa binária Python
Harshit Jindal 30 janeiro 2023
Python Python Algorithm
  1. Algoritmo de pesquisa binária
  2. Programa Python para pesquisa binária
Pesquisa binária Python

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 como 0 e hi como n - 1.
  • Enquanto lo <hi, defina mid = lo + (hi - lo)/2.
    • Se A[mid] == X, encontramos o elemento que retorna o índice mid.
    • Se A[mid] < X, descarte a metade esquerda dos elementos e defina lo como mid+1.
    • Caso contrário, se A[mid]> X, descarte a metade direita dos elementos e defina hi como mid-1.
  • 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 avatar Harshit Jindal avatar

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

Artigo relacionado - Python Algorithm