Algoritmo de pesquisa binária (Binary Search) em C++- explicação, exemplo e código

O algoritmo de pesquisa binária é uma maneira mais eficiente de pesquisar um elemento específico em uma lista classificada. Ao contrário da pesquisa linear, que verifica os elementos sequencialmente, a pesquisa binária divide a lista em metades e compara o elemento de destino com o elemento do meio. Esse processo é repetido até que o elemento de destino seja encontrado ou o intervalo de pesquisa fique vazio.

Como funciona

1. Comece com toda a lista classificada.
2. Encontre o elemento do meio do intervalo de pesquisa atual.
3. Compare o elemento do meio com o valor alvo.
4. Se o elemento do meio for igual ao valor de destino, a pesquisa foi bem-sucedida.
5. Se o elemento do meio for maior que o alvo, procure na metade esquerda do intervalo.
6. Se o elemento do meio for menor que o alvo, procure na metade direita do intervalo.
7. Repita as etapas 2 a 6 até que o elemento de destino seja encontrado ou o intervalo de pesquisa fique vazio.

Exemplo

Vamos considerar uma lista ordenada de números inteiros e queremos encontrar o número 34 usando pesquisa binária.

Lista classificada: {12, 23, 34, 45, 56, 67, 89, 90}

1. Comece com a lista inteira.
2. Elemento do meio: 56(posição 4). Compare com 34.
3. 56 é maior que 34. Pesquise na metade esquerda.
4. Novo elemento do meio: 23(posição 1). Compare com 34.
5. 23 é menor que 34. Pesquise na metade direita.
6. Novo elemento do meio: 45(posição 3). Compare com 34.
7. 45 é maior que 34. Pesquise na metade esquerda.
8. Novo elemento do meio: 34(posição 2). Alvo encontrado.

Exemplo de código em C++

#include <iostream>  
#include <vector>  
  
int binarySearch(const std::vector<int>& arr, int target) {  
    int left = 0;  
    int right = arr.size()- 1;  
  
    while(left <= right) {  
        int mid = left +(right- left) / 2;  
  
        if(arr[mid] == target) {  
            return mid;  
        } else if(arr[mid] < target) {  
            left = mid + 1;  
        } else {  
            right = mid- 1;  
        }  
    }  
  
    return -1;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 34, 45, 56, 67, 89, 90};  
    int target = 34;  
  
    int result = binarySearch(numbers, target);  
  
    if(result != -1) {  
        std::cout << "Element " << target << " found at position " << result << std::endl;  
    } else {  
        std::cout << "Element " << target << " not found in the array" << std::endl;  
    }  
  
    return 0;  
}  

No exemplo dado, a binarySearch função é usada para encontrar o número 34 em uma lista ordenada de números inteiros. O resultado será a posição 34 na lista(as posições começam em 0) ou -1 se o número não for encontrado.