Programmieren
Von: , Frage gestellt am Mi, 22. Okt 2003
Wie kann ich die lineare und binäre Suche berechnen? Habt Ihr vielleicht ein einfaches Rezept dafür?
Vielen Dank im Voraus,
Maja Fritz
1 Antworten zu dieser Frage
-
Antwort von nach 21 Stunden 0 hilfreich
Re: Programmieren
Wie kann ich die lineare und binäre Suche berechnen? Habt Ihr
vielleicht ein einfaches Rezept dafür?
Naja, also mit berechnen ist da nicht viel. Du meinst wahrscheinlich lineare bzw. binäre Suche in einem Feld/Array...
Linear : Jedes Element von 0 bis Ende durchsuchen/vergleichen, bis du das entsprechende Element gefunden hast.
Binär : Feld muss aufsteigend sortiert sein!
1. linke grenze = 0 / rechte Grenze = letztes Element
Mitte = links + rechts / 2
2. Solange links <= rechts mache
3. Wenn das Element in der Mitte kleiner ist als das gesuchte Element (Feld[Mitte] < gesuchtes Element), dann linke Grenze nach rechts verschieben (links = Mitte + 1)
4. Sonst, Wenn das Element in der Mitte grösser ist als das gesuchte Element (Feld[Mitte] > gesuchtes Element), dann rechte Grenze nach links verschieben (rechts = Mitte - 1)
5. Sonst Element gefunden, abbrechen
6. gehe zu 2.
Der Trick ist, das linare Suche im schlimmsten Fall n Vergleiche braucht, binäre Suche aber viel weniger.
Fündig wird man da auch in "Algorithmen in C", "Datenstrukturen" Büchern, etc...
KIM