Startseite   |  Site map   |  A-Z artikel   |  Artikel einreichen   |   Kontakt   |  
   
  •  
    Biologie
    Themen der Chemie
    Deutsch online artikel
    Englisch / Englische
    Franzosisch
    Geographie
    Geschichte
    Informatik
    Kunst
    Mathematik / Studium
    Musik
    Philosophie
    Physik
    Recht
    Sport
    Wirtschaft & Technik



    Biographie

    Impressum

informatik artikel (Interpretation und charakterisierung)

Suche

Binäre suche (binary search)


1. Java
2. Viren



Die Suchzeit kann gegenüber der sequentiellen Suche verringert werden, indem man ein sortiertes Feld durchsucht. Das Feld wird in zwei Hälften geteilt, und festgestellt in welcher Hälfte des Feldes sich der gesuchte Datensatz befindet. Diese Methode wird dann rekursiv angewandt, bis nur mehr ein Datensatz übrig ist. Dieser kann der gesuchte sein, oder den Datensatz mit dem gesuchten Schlüssel gibt es nicht. Im Beispiel wird nach der Zahl 13 gesucht:



Binäre Suche erfordert sowohl für erfolgreiche als auch für erfolglose Suche niemals mehr als lg(N+1) Vergleiche.

Dies gilt, weil bei jedem Schritt die Anzahl der Datensätze halbiert wird. Ein Problem entsteht bei nicht eindeutigen Schlüsseln. Wenn während der Suche ein gesuchter Datensatz gefunden wird, müssen dann nämlich auch dessen Nachbarn durchsucht werden.

Die Folge der Vergleiche ist beim binären Suchen vorbestimmt, und kann in einem binären Baum dargestellt werden. Später werden noch Algorithmen beschrieben, die speziell konstruierte Baumstrukturen zur Steuerung der Suche benötigen.



2.1 Interpolationssuche (interpolation search)
Diese stellt eine mögliche Verbesserung dar. Hier versucht man genauer zu erraten, wo sich das gesuchte Element befindet. Dies erinnert an die Suche in einem Telefonbuch, wo man eher vorne zu suchen beginnt, wenn der gesuchte Name mit einem B beginnt. Im Beispiel wird wieder nach der 13 gesucht:



Interpolationssuche erfordert für erfolgreiche aber auch für erfolglose Suche niemals mehr als lg[lg(N+1)] Vergleiche.

Die Interpolationssuche ist besonders für große, gleichmäßig verteilte Felder geeignet, da z. B. für eine Milliarde Elemente nur maximal 5 Schritte erforderlich wären. Ein Nachteil ist, das die Interpolationssuche bei einer sehr ungleichmäßigen Verteilung hereingelegt werden kann. Bei kleinen Feldern ist auch der Vorteil der durch die Interpolation entsteht sehr gering.

 
 




Datenschutz

Top Themen / Analyse
Die Darstellungschicht (Presentation Layer)
Die drei Layer
Schleifen
BIOS - Optimal konfigurieren
Sicherheit
Erzeugung des Huffman-Codes (Building the Huffman Code)
Behandlung von Laufzeitfehlern in Visual Basic-
Grundprinzip und Schriftarten
Identifikation von Sender und Empfänger
Technik mit JAVA:





Datenschutz

Zum selben thema
Netzwerk
Software
Entwicklung
Windows
Programm
Unix
Games
Sicherheit
Disk
Technologie
Bildung
Mp3
Cd
Suche
Grafik
Zahlung
Html
Internet
Hardware
Cpu
Firewall
Speicher
Mail
Banking
Video
Hacker
Design
Sprache
Dvd
Drucker
Elektronisches
Geschichte
Fehler
Website
Linux
Computer
A-Z informatik artikel:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z #

Copyright © 2008 - : ARTIKEL32 | Alle rechte vorbehalten.
Vervielfältigung im Ganzen oder teilweise das Material auf dieser Website gegen das Urheberrecht und wird bestraft, nach dem Gesetz.