Pesquisa Binária

1. Algoritmo de pesquisa binária
2. Exemplo de pesquisa binária
3. Implementação de algoritmo de pesquisa binária
4. Complexidade do algoritmo de pesquisa binária

A pesquisa binária é o algoritmo de pesquisa mais popular e eficiente. Na verdade, é o algoritmo de busca mais rápido. Assim como o jump sort, ele também precisa que o array seja classificado. É baseado na abordagem de dividir e conquistar, na qual dividimos o array em duas metades e, em seguida, comparamos o item que procuramos com o item do meio. Se o item do meio corresponder, retornamos o índice do elemento do meio; caso contrário, movemos para a metade esquerda e direita dependendo do valor do item.

Algoritmo de pesquisa binária

Vamos supor que temos um array não classificado A[] contendo n elementos, e queremos encontrar um elemento X.

Exemplo de pesquisa binária

Suponha que temos a matriz: (1, 2, 3, 4, 5, 6, 7, 8, 9), e queremos encontrar X - 8.

Implementação de algoritmo de pesquisa binária

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int lo, int hi, int x) {
  while (lo <= hi) {
    int m = lo + (hi - lo) / 2;
    if (arr[m] == x) return m;
    if (arr[m] < x)
      lo = m + 1;
    else
      hi = m - 1;
  }
  return -1;
}

int main(void) {
  int n = 9;
  int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9};
  int x = 8;
  int result = binarySearch(arr, 0, n - 1, x);
  if (result == -1) {
    cout << "Element not found !!";
  } else
    cout << "Element found at index " << result;
  return 0;
}

Complexidade do algoritmo de pesquisa binária

Complexidade de tempo

• Caso Médio

Quando realizamos a pesquisa binária, pesquisamos em uma metade e descartamos a outra metade, reduzindo o tamanho do array pela metade a cada vez.

A expressão para complexidade de tempo é dada pela recorrência.

T(n) = T(n/2) + k , k is a constant.

Este resultado desta recorrência dá logn, e a complexidade do tempo é da ordem de O(logn). É mais rápido do que a pesquisa linear e a pesquisa de salto.

• Melhor caso

O melhor caso ocorre quando o elemento do meio é o elemento que estamos procurando e é retornado na primeira iteração. O melhor caso de complexidade de tempo é O(1).

• Pior caso

A complexidade de tempo do pior caso é igual à complexidade de tempo do caso médio. O pior caso de complexidade de tempo é O(logn).

Complexidade do Espaço

A complexidade de espaço deste algoritmo é O(1) no caso de implementação iterativa porque não requer nenhuma estrutura de dados além de variáveis ​​temporárias.

No caso de implementação recursiva, a complexidade do espaço é O(logn) devido ao espaço requerido pela pilha de chamadas recursivas.