Implementierung des binären Suchalgorithmus auf einem sortierten Array

Implementierung des binären Suchalgorithmus in C auf einem sortierten Integer-Array mit effizienter O(log n) Komplexität und Beispielcode.

Kurze Einführung

Implementierung des binären Suchalgorithmus auf einem sortierten Array (c)
BESCHREIBUNG:
Dieses Beispiel zeigt, wie man in C den binären Suchalgorithmus auf einem aufsteigend sortierten Integer-Array implementiert. Die Funktion gibt den Index des gesuchten Elements zurück oder -1, wenn das Element nicht vorhanden ist.

WEITERE HINWEISE:
Der binäre Suchalgorithmus erfordert, dass das Array aufsteigend sortiert ist. Die Funktion ist effizient mit einer Komplexität von O(log n). Der Code ist bereit, mit jedem Standard-C-Compiler ohne externe Abhängigkeiten kompiliert zu werden.

ERKLÄRUNGEN:
- Die Funktion ricercaBinaria verwendet zwei Indizes, low und high, um den zu untersuchenden Array-Abschnitt abzugrenzen.
- Sie berechnet den mittleren Index mid als low + (high - low) / 2, um Überlaufprobleme bei sehr großen Indizes zu vermeiden.
- Wenn das Element an Position mid gleich dem gesuchten Wert ist, gibt sie den Index mid zurück.
- Ist das Element an mid kleiner als der gesuchte Wert, wird low auf mid + 1 gesetzt, um in der rechten Hälfte zu suchen.
- Ist das Element an mid größer, wird high auf mid - 1 gesetzt, um in der linken Hälfte zu suchen.
- Die while-Schleife läuft, solange low kleiner oder gleich high ist; wenn das Element nicht gefunden wird, gibt sie -1 zurück.
- Im main wird ein sortiertes Array definiert, der zu suchende Wert angegeben, die Funktion aufgerufen und das Ergebnis ausgegeben.

Beispielcode: c

#include <stdio.h>

// Funktion, die die binäre Suche auf einem sortierten Array durchführt
// Parameter:
// - arr: Zeiger auf das sortierte Array
// - size: Größe des Arrays
// - target: zu suchender Wert
// Rückgabe: Index des Elements, wenn gefunden, sonst -1
int ricercaBinaria(int *arr, int size, int target) {
    int low = 0;
    int high = size - 1;

    while (low <= high) {
        // Berechnung des mittleren Index unter Vermeidung von Überlauf
        int mid = low + (high - low) / 2;

        if (arr[mid] == target) {
            return mid; // Element gefunden
        } else if (arr[mid] < target) {
            low = mid + 1; // Suche in der rechten Hälfte
        } else {
            high = mid - 1; // Suche in der linken Hälfte
        }
    }

    return -1; // Element nicht gefunden
}

int main() {
    // Beispiel für ein sortiertes Array
    int arrayOrdinato[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int dimensione = sizeof(arrayOrdinato) / sizeof(arrayOrdinato[0]);

    int valoreDaCercare = 23;

    // Aufruf der binären Suchfunktion
    int indice = ricercaBinaria(arrayOrdinato, dimensione, valoreDaCercare);

    if (indice != -1) {
        printf("Wert %d an Index %d gefunden.\n", valoreDaCercare, indice);
    } else {
        printf("Wert %d nicht im Array gefunden.\n", valoreDaCercare);
    }

    return 0;
}
×
×
×
Möchtest du die Antwort neu generieren?
×
Chat exportieren
Exportformat wählen
Generazione PDF in corso…
Allegati
×
Du bist dabei, den Chat zu schließen und zum Bildgenerator zu wechseln. Wenn du nicht eingeloggt bist, wirst du unseren Chat verlieren. Bestätigst du?
Du siehst einen geteilten Chat im temporären Modus. Er wird nicht gespeichert.
×
Gespeicherte Prompts
×
Private Notiz
×
Bezeichnung
×
In allen Chats suchen
×
Deine Erkenntnisse
Analyse läuft…
×
KI-Einstellungen
Name des Assistenten 30
Länge der Antworten
KI-Modell
Strukturierte Antworten
Beispiele einbeziehen
Emojis verwenden
Führe mich, löse nicht Hinweise und Fragen statt fertiger Lösung
Mehr Einstellungen →
×
Diesen Chat teilen
Wer diesen Link öffnet, kann den Chat ansehen oder ihn als eigenen Chat zum Profil hinzufügen.
Achtung: Auch die Anhänge des Chats werden geteilt. Wer ihn hinzufügt, erhält eine Kopie der Dateien im eigenen Ordner.
Geteilter Chat
Jemand hat einen Chat mit dir geteilt. Möchtest du ihn nur ansehen oder zu deinen Chats hinzufügen?
Achtung: Auch die Anhänge des Chats werden geteilt. Wer ihn hinzufügt, erhält eine Kopie der Dateien im eigenen Ordner.
×

Gespeicherte Nachrichten

Wird geladen...

×

Chat-Verlauf

beispiel-programme · CHAT-VERLAUF

Wird geladen...

KI-Einstellungen

×
  • BasisSchnelle und einfache Antworten zum Lernen
  • MittelHöhere Qualität für Studium und Programmierung
  • FortgeschrittenKomplexes Denken und detaillierte Analysen
Schritte erklären

Was wird benötigt?

Sortiertes Integer-Array: die Eingabe, auf der die binäre Suche ausgeführt wird.

Binäre Suchfunktion: implementiert den klassischen Algorithmus mit Verwaltung der Indizes low, high und mid.

Main-Funktion: definiert ein Beispiel-Array, ruft die Suchfunktion auf und gibt das Ergebnis aus.

Software-Konfiguration: Standard-C-Compiler (z.B. gcc), keine externen Bibliotheken erforderlich.

Ausführungsumgebung: jedes System mit Standard-C-Compiler.

Pinout/Hardware: nicht anwendbar (reine Software).

Ähnliche Themen

Berechnung des Durchschnitts von drei Ganzzahlen
C-Programm zur Berechnung des Durchschnitts von drei Ganzzahlen mit Eingabe über Tastatur und Ausgabe des Ergebnisses als Gleitkommazahl auf der Konsole.
Ausgabe des 5er Einmaleins
Ein einfaches C-Programm gibt das 5er Einmaleins von 1 bis 1 mit einer for-Schleife aus und ist ideal für Anfänger geeignet.
Zeichen in einem String zählen ohne strlen zu verwenden
Ein einfaches C-Beispiel zeigt, wie man die Anzahl der Zeichen in einem String ohne strlen zählt, indem man den String manuell bis zum Terminator durchläuft.
Programm, das ein Zeichen liest und dessen ASCII-Code anzeigt
Ein einfaches C-Programm liest ein Zeichen von der Tastatur und zeigt dessen ASCII-Code an. Ideal für Anfänger mit getchar und printf Funktionen.
Berechnung des Umfangs eines Kreises bei gegebenem Radius
C-Programm zur Berechnung des Kreisumfangs basierend auf dem eingegebenen Radius mit genauer Ausgabe und Verwendung von float und PI Konstante.
Suche nach einer Zahl in einem kleinen Array (lineare Suche)
Einfaches Beispiel für lineare Suche in einem Integer-Array in C. Das Programm prüft, ob eine Zahl im Array vorhanden ist und gibt das Ergebnis aus.
Programm, das Vokale in einem String zählt
Ein einfaches C-Programm zählt Vokale in einem String. Es nutzt fgets und tolower für sichere Eingabe und genaue Vokalzählung in Groß- und Kleinbuchstaben.
Programm, das Leerzeichen in einem String durch Unterstriche ersetzt
Dieses C-Programm ersetzt Leerzeichen in einem String durch Unterstriche und zeigt einfache Stringmanipulation mit sicherer Eingabe und modularer Funktion.