Localizando a Primeira Ocorrência em um Array Ordenado

Introdução

Neste laboratório, aprenderemos como encontrar a primeira ocorrência de um número dado em um array ordenado usando busca binária modificada em C++.

O arquivo de código C++

Primeiramente, vamos criar um arquivo de código C++ chamado main.cpp no diretório ~/project usando o editor de texto touch.

touch ~/project/main.cpp

Inclua os headers necessários no código

Precisamos incluir os arquivos de cabeçalho C++ necessários em nosso programa. Copie e cole o seguinte código em seu arquivo main.cpp.

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

Crie uma função para encontrar a primeira ocorrência de um elemento

Criaremos uma função chamada first() que recebe um array, seu índice inferior, índice superior e o elemento a ser pesquisado como entrada. A função retornará o índice da primeira ocorrência do elemento. Inclua o seguinte código no arquivo main.cpp.

int first(int a[], int l, int h, int b)
{
    int res = -1;
    while (l <= h)
    {
        int m = (l + h) / 2;
        if (a[m] == b)
        {
            res = m;
            h = m - 1;
        }
        else if (a[m] > b)
        {
            h = m - 1;
        }
        else
        {
            l = m + 1;
        }
    }
    return res;
}

Aqui, usamos a busca binária (binary search) para encontrar a primeira ocorrência do elemento. Inicializamos a variável res com -1 para tratar o caso em que o elemento não está presente no array. Se o elemento do meio for igual ao elemento que estamos procurando, armazenamos o índice do elemento do meio em res e atualizamos o índice superior para m-1, pois estamos procurando a primeira ocorrência do elemento. Se o elemento do meio for maior que o elemento que estamos procurando, atualizamos o índice superior para m-1, e se for menor que o elemento, atualizamos o índice inferior para m+1.

Implemente a função principal

Na função principal, criaremos um array, chamaremos a função first criada no Passo 3 com os argumentos apropriados e exibiremos o resultado no console. Copie e cole o código abaixo na função main.

int main()
{
    int a[] = {2, 3, 3, 4, 4, 4, 4, 4, 5};

    int n = sizeof(a) / sizeof(a[0]);

    int k = 4; //the element to find the first occurrence index of

    int f = first(a, 0, n - 1, k);

    if(f==-1)
    {
        cout << "Element not found\n";
    }
    else
    {
        cout << "The index of the first occurrence of " << k << " is: " << f << endl;
    }

    return 0;
}

Aqui, declaramos um array de inteiros chamado a e o inicializamos com valores inteiros ordenados. Também calculamos o número de elementos no array usando o operador sizeof. Em seguida, chamamos a função first() com os argumentos apropriados e exibimos o resultado.

Compile e execute o código C++

Agora, podemos compilar e executar o código C++ usando os seguintes comandos.

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

Se tudo correr bem, a saída será The index of the first occurrence of 4 is: 3.

Resumo

Neste laboratório, aprendemos como encontrar a primeira ocorrência de um número em um array ordenado usando busca binária modificada em C++. Criamos uma função first() para implementar o algoritmo.