Binäre Suche: Unterschied zwischen den Versionen
(Die Seite wurde neu angelegt: „'''Binäre Suche''' Bei der binären Suche wird nach einem Objekt in einem Array mit folgendem Algorythmen gesucht: ''Iterative Suche'' Zuerst wird die Mitte…“) |
|||
| Zeile 1: | Zeile 1: | ||
| − | ''' | + | '''Iterative Suche''' |
| − | + | ||
Bei der binären Suche wird nach einem Objekt in einem Array mit folgendem Algorythmen gesucht: | Bei der binären Suche wird nach einem Objekt in einem Array mit folgendem Algorythmen gesucht: | ||
| − | |||
| − | |||
Zuerst wird die Mitteberechnet indem die linke Schranke mit dem Quotienten aus der Differenz der rechten und linken Schranke und zwei (mitte = links + (rechts - links)/2). | Zuerst wird die Mitteberechnet indem die linke Schranke mit dem Quotienten aus der Differenz der rechten und linken Schranke und zwei (mitte = links + (rechts - links)/2). | ||
Dann wird geguckt ob die errechnete Mitte das gesuchte Objekt ist. | Dann wird geguckt ob die errechnete Mitte das gesuchte Objekt ist. | ||
| Zeile 12: | Zeile 9: | ||
Falls die linke Schranke Rechts von der rechten ist (oder umgekehrt), so wird angegeben, dass das gesuchte Objekt nicht existiert. | Falls die linke Schranke Rechts von der rechten ist (oder umgekehrt), so wird angegeben, dass das gesuchte Objekt nicht existiert. | ||
| − | ''Rekursive Suche'' | + | '''Rekursive Suche''' |
Die rekursive Suche funktioniert fast gleich, nur dass die Mitte aus dem Quotienten der Summe aus links und rechts und zwei berechnet wird ((links + rechts)/2). | Die rekursive Suche funktioniert fast gleich, nur dass die Mitte aus dem Quotienten der Summe aus links und rechts und zwei berechnet wird ((links + rechts)/2). | ||
| + | |||
| + | [[Datei:binäreSucheBild.jpg]] | ||
Version vom 6. Dezember 2016, 13:41 Uhr
Iterative Suche Bei der binären Suche wird nach einem Objekt in einem Array mit folgendem Algorythmen gesucht: Zuerst wird die Mitteberechnet indem die linke Schranke mit dem Quotienten aus der Differenz der rechten und linken Schranke und zwei (mitte = links + (rechts - links)/2). Dann wird geguckt ob die errechnete Mitte das gesuchte Objekt ist. Ist sie es, so ist die Suche beendet, ist sie es nicht so wird geguckt ob das Objekt größer sein muss als die errechnete Mitte. Ist der Wert größer so gilt: links = mitte +1. Ist der Wert kleiner so gilt : rechts = miite -1. Dieser Vorgang wird so lange wiederholt bis das entsprechende Objekt gefunden wurde. Falls die linke Schranke Rechts von der rechten ist (oder umgekehrt), so wird angegeben, dass das gesuchte Objekt nicht existiert.
Rekursive Suche Die rekursive Suche funktioniert fast gleich, nur dass die Mitte aus dem Quotienten der Summe aus links und rechts und zwei berechnet wird ((links + rechts)/2).
