Busca Binária em C++ Usando Array Dinâmico

Introdução

A busca binária (binary search) é um método de busca que encontra a posição do índice de um elemento em um array ordenado. Em C++, podemos realizar uma busca binária usando duas abordagens - iterativa e recursiva. Neste laboratório, realizaremos uma operação de busca binária usando um array dinâmico.

Criar um novo arquivo C++

Primeiramente, criamos um novo arquivo C++ no diretório ~/project chamado main.cpp.

touch ~/project/main.cpp

Incluir arquivos de cabeçalho

Em seguida, incluímos os arquivos de cabeçalho necessários - iostream, algorithm e vector.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

Criar um array dinâmico e preenchê-lo com elementos

Criamos um array dinâmico de inteiros usando a classe vector e o populamos com inteiros ordenados.

vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};

Implementar função de busca binária

Em seguida, implementamos a função de busca binária que procura a posição do índice de um elemento em um array ordenado usando a abordagem iterativa.

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

Chamar a função de busca binária e exibir o resultado

Finalmente, chamamos a função de busca binária com um elemento para procurar e exibimos o resultado no console.

int target = 7;
int result = binarySearch(arr, target);

if (result == -1) {
    cout << "Element not found!" << endl;
} else {
    cout << "Element found at index " << result << endl;
}

Compilar e executar o programa

Compile e execute o programa no terminal executando o seguinte comando:

g++ main.cpp -o main && ./main

Código final

Aqui está o código completo do arquivo main.cpp:

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int binarySearch(vector<int> arr, int target) {
    int low = 0;
    int high = arr.size() - 1;
    int mid;

    while (low <= high) {
        mid = (low + high) / 2;

        if (arr[mid] == target) {
            return mid;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }

    return -1;
}

int main() {
    vector<int> arr = {1, 3, 5, 7, 9, 11, 13, 15};
    int target = 7;
    int result = binarySearch(arr, target);

    if (result == -1) {
        cout << "Element not found!" << endl;
    } else {
        cout << "Element found at index " << result << endl;
    }

    return 0;
}

Resumo

Neste laboratório, aprendemos como realizar a busca binária (binary search) usando um array dinâmico em C++. Usamos a abordagem iterativa e implementamos uma função de busca binária para procurar a posição do índice de um elemento em um array ordenado. Também aprendemos como criar um array dinâmico usando a classe vector em C++.