Das erste Vorkommen in einem sortierten Array finden

Einführung

In diesem Lab werden wir lernen, wie man mithilfe einer modifizierten binären Suche in C++ den ersten Vorkommen einer gegebenen Zahl in einem sortierten Array findet.

Skills Graph

Die C++-Code-Datei

Zunächst erstellen wir eine C++-Code-Datei namens main.cpp im Verzeichnis ~/project mit dem Texteditor touch.

touch ~/project/main.cpp

Fügen Sie in den Code die erforderlichen Headerdateien hinzu

Wir müssen in unserem Programm die erforderlichen C++-Headerdateien hinzufügen. Kopieren und einfügen Sie den folgenden Code in Ihre main.cpp-Datei.

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

Erstellen Sie eine Funktion, um den ersten Vorkommen eines Elements zu finden

Wir werden eine Funktion namens first() erstellen, die ein Array, seinen unteren Index, oberen Index und das zu suchende Element als Eingabe nimmt. Die Funktion wird den Index des ersten Vorkommens des Elements zurückgeben. Fügen Sie den folgenden Code in die main.cpp-Datei ein.

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;
}

Hier haben wir die binäre Suche verwendet, um das erste Vorkommen des Elements zu finden. Wir haben die Variable res mit -1 initialisiert, um den Fall zu behandeln, wenn das Element nicht im Array vorhanden ist. Wenn das mittlere Element dem Element entspricht, das wir suchen, speichern wir den Index des mittleren Elements in res und aktualisieren den oberen Index auf m-1, da wir das erste Vorkommen des Elements suchen. Wenn das mittlere Element größer als das Element ist, das wir suchen, aktualisieren wir den oberen Index auf m-1, und wenn es kleiner ist, aktualisieren wir den unteren Index auf m+1.

Implementieren Sie die Hauptfunktion

In der Hauptfunktion werden wir ein Array erstellen, die in Schritt 3 erstellte first-Funktion mit den entsprechenden Argumenten aufrufen und das Ergebnis in der Konsole ausgeben. Kopieren und einfügen Sie den folgenden Code in die main-Funktion.

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

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

    int k = 4; //das Element, dessen ersten Vorkommensindex gefunden werden soll

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

    if(f==-1)
    {
        cout << "Element nicht gefunden\n";
    }
    else
    {
        cout << "Der Index des ersten Vorkommens von " << k << " ist: " << f << endl;
    }

    return 0;
}

Hier haben wir ein Array von ganzen Zahlen namens a deklariert und es mit sortierten ganzzahligen Werten initialisiert. Wir haben auch die Anzahl der Elemente im Array mithilfe des sizeof-Operators berechnet. Anschließend haben wir die first()-Funktion mit den entsprechenden Argumenten aufgerufen und das Ergebnis ausgegeben.

Kompilieren und Ausführen des C++-Codes

Jetzt können wir den C++-Code mit den folgenden Befehlen kompilieren und ausführen.

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

Wenn alles erfolgreich verläuft, wird die Ausgabe lauten: Der Index des ersten Vorkommens von 4 ist: 3.

Zusammenfassung

In diesem Lab haben wir gelernt, wie man mithilfe einer modifizierten binären Suche in C++ den ersten Vorkommen einer gegebenen Zahl in einem sortierten Array findet. Wir haben eine first()-Funktion erstellt, um das Algorithmus umzusetzen.