Binäre Suche im Array // C

Chris_90

Moin Leute,
ich komme grade nicht weiter.
Ich möchte eine Funktion schreiben, die mir eine Zahl in einem Array (Feld) sucht.
Also, ich habe eine beliebig langes Array vom Typ integer. In diesem Array stehen nur positive Zahlen, die aufsteigend sortiert sind. also zb:

int a[5] = {2,7,13,14,21}

Es wird nun eine Zahl einge geben und mit Hilfe der binären Suche soll herausgefunden werden, ob die Zahl in diesem Array liegt.
Wie die Suche ansich funktioniert weiß ich.
Das Feld wird aufgeteilt, dann wir in dem linken geschaut ob die Zahl kleiner als die letzte Zahl des linken Felds ist, wenn das der Fall ist, wird das Feld wieder aufgeteilt und so weiter... man nähert sich der Zahl dann an, bis man sie hat, oder das Programm quasi herausfindet, dass die Zahl nicht in diesem Array liegt.
Es wird also immer um die hälfte aufgeteilt.
Mein Problem ist nun, dass ich nicht wirklich weiß, wie ich das in geeigneten Programmcode umsetze.
Kann mir da jemand helfen?
Danke schonmal,
Chris

SeppJ

Sprich: Du möchtest deine Hausaufgaben gemacht haben und bist sogar zu faul um selber den Pseudocode auf Wikipedia zu übersetzen?

auf wikipedia gibts soagar ne lauffähige c-version.

Chris_90

Nein, ich möchte nicht meine Hausaufgaben gemacht bekommen...
ich hab doch nur ledigliche gefragt, ob mir jemand helfen kann... ich hab nirgendwo gefragt, ob jemand mir das löse kann.
ich weiß halt nur nicht, mit welchem befehl ich den array aufteilen kann.
sodass ich quasi 2 arrays habe. mit dem linken teil des arrays habe ich auch nicht so das problem, mit dem rechten schon, aber danke, dass man so hilfsbereit ist und mir sagt, dass ich meine hausaufgaben gemacht bekommen haben will...
den komentar hättet ihr euch auch sparen können!

314159265358979

Du brauchst das Array nicht aufzuteilen.

Chris_90

aber wie suche ich dann weiter?
wie sage ich dass mein programm weiter suchen soll, wenn die zahl nicht im linken teil des halbierten arrays ist? ich versteh nicht den schritt, wie ich dann sage, dass er im rechtn teil weitersuchen soll.
wenn mein array 10 integer werte hat und ich ihn halbiere, durchsuche ich die ersten 5. wenn die zahl da nicht drin ist, wie sage ich ihm, dass er ab dem 6. element bis zum 10. suchen soll?

SeppJ

Du schreibst eine Funktion, die nimmt kein Array entgegen, sondern den Anfang und den Ende des Suchbereichs entgegen. Und dann rufst du aus dieser Funktion wieder diese Funktion auf, aber mit der Hälfte des Suchbereichs.

Das kann man nach dem gleichen Schema auch ohne Rekursion machen, aber mit Funktionen ist es recht gut verständlich.

Wutz

Du hast auch vergessen zu erwähnen, dass dein Arrayinhalt sortiert vorliegen muss damit dein beschriebener Algorithmus funktioniert.

So ist aber die Vorgabe:

Chris_90 schrieb:

In diesem Array stehen nur positive Zahlen, die aufsteigend sortiert sind.

Es gibt im C-Standard vorgefertigt eine Funktion bsearch, die analog zu qsort funktioniert. Beispiel:

#include <stdlib.h>

int int_compare(void const *lhs, void const *rhs) {
  return *(int const *)lhs < *(int const *)rhs;
}

/* ... */

int daten[] = { 2, 7, 13, 14, 21 };
int key = 13;
int *pos;

pos = bsearch(&key, daten, 5, sizeof(int), int_compare);

Shiba

Was hindert Dich den Hinweis auf die C Implementierung unter Binäre Suche bei Wikipedia zu nutzen und zu untersuchen?
M.E. zeigt die dortige Source sehr gut wie es geht.