Binäre suche Rekursiv
-
Hallo ich habe eine frage. ich soll einen binären suchalgorithmus rekursiv nachprogrammieren aber habe keine ahnung wie!
dies ist der ausganspunkt
int binSearch(int array[], int Suchwert, int array_size) { int low = 0; int high = array_size; int mid; while (low <= high) { mid = (low+high)/2; if (Suchwert < array[mid]) high = mid-1; else if (Suchwert > array[mid]) low = mid+1; else return mid; // gefunden } return (-1); // nicht gefunden }ich hoffe das ich hier jemand finde der mir helfen kann
-
Wozu das? Für die Geschwindigkeit macht es keinen Unterschied, ob du rekursiv oder iterativ suchst (da dürfte eher die iterative Variante schneller sein).
Ansonsten hilft sicher auch ein Blick in die Wikipedia - binäre Suche (ziemlich weit unten ist auch die rekursive Variante für Python angegeben)
-
MaxMax schrieb:
Hallo ich habe eine frage. ich soll einen binären suchalgorithmus rekursiv nachprogrammieren aber habe keine ahnung wie!
Das ist eine sehr ungewöhnliche Aufgabenstellung, da der rekursive Algorithmus viel einfacher durch kurzes Nachdenken zu finden ist als durch Umbauen des iterativen Algorithmus'. Es ist eher eine Transformation rekursiv->iterativ denkbar.
-
weißt du was rekursiv bedeutet?
ich frage mich auch warum man den gesuchten wert zurückgibt...ist doch eigentlich klar welcher das ist und was passiert wenn ich mal -1 suche?...ich würde dafür nen bool nehmen.bool binSearch(int arr[], int Suchwert, int low, int high){ int mid = ((high-low)/2)+low; //mitte bestimmen, so ungefähr... if( arr[mid] == Suchwert ) return gefunden; if( low == high ) return nicht gefunden; if(arr[mid] > Suchwert) return rechtesuche; if(arr[mid] < Suchwert) return linkesuche; }so ungefähr würde ich das machen
-
ConfusedGuy schrieb:
ich frage mich auch warum man den gesuchten wert zurückgibt...
Macht er doch gar nicht. Er gibt den Index zurück, wenn es gefunden wurde, und -1, wenn nicht.
-
ups ^^ verpeilt. ist noch zu früh am morgen...