Logo Logo
InfoHome Themen Projekte Links Software
Themen
JavaHamster
BlueJ
Java
Sprachelemente
Abstrakte Datentypen
Swing
Sortieren
Binäre Suche
InsertionSort
SelectionSort
BubbleSort
ShakerSort
Quicksort
MergeSort
Komplexität
HTML
XHTML
CSS
XML
Datenbanken
MySQL
Theoretische Informatik
PHP
Kara
Lego-Roboter
Algorithmen

Binäre Suche

Die binäre Suche ist ein Algorithmus, der auf einem Array recht schnell ein gesuchtes Element findet bzw. eine zuverlässige Aussage über das Fehlen dieses Elementes liefert. Voraussetzung ist, dass die Elemente des Array in einer dem Suchbegriff entsprechenden Weise sortiert sind. Der Algorithmus basiert auf dem Schema Teile und Herrsche (divide & conquer).

Algorithmus

Zuerst wird das mittlere Element des Arrays überprüft. Es kann kleiner, größer oder gleich dem gesuchten Element sein. Ist es kleiner als das gesuchte Element, muss das gesuchte Element in der hinteren Hälfte stecken, falls es sich dort überhaupt befindet. Ist es hingegen größer, muss nur in der vorderen Hälfte weitergesucht werden. Die jeweils andere Hälfte muss nicht mehr betrachtet werden. Ist es gleich dem gesuchten Element, ist die Suche (vorzeitig) beendet.

Jede weiterhin zu untersuchende Hälfte wird wieder gleich behandelt: Das mittlere Element liefert wieder die Entscheidung darüber, wo bzw. ob weitergesucht werden muss.

Die Länge des Suchbereiches wird von Schritt zu Schritt halbiert. Spätestens wenn der Suchbereich auf 1 Element geschrumpft ist, ist die Suche beendet. Dieses eine Element ist entweder das gesuchte Element, oder das gesuchte Element kommt nicht vor.

Der Algorithmus zur binären Suche wird entweder iterativ oder rekursiv implementiert. In der Mathematik ist er bekannt als Intervallschachtelung.

Implementation

/**
 * BINARY SEARCH
 * Algorithmus zur BINÄEREN SUCHE, hier so implementiert,
 * dass die Array-Position zurückliefert wird, an der ein int-Wert
 * in ein der Größe nach aufsteigend geordnetes int-Array eingefügt
 * werden muss, so dass die Ordnung bestehen bleibt.
 *
 * @param a int-Array auf dem gesucht werden soll
 * @param value einzufügender int-Wert
 * @param l Indexwert für linke Intervallgrenze des aktuellen Teilarrays
 * @param r Indexwert für rechte Intervallgrenze des aktuellen Teilarrays
 *
 * @return die Indexposition, an der das Element value in das Array eingefügt werden soll
 */

public static int binsearch(int[] a, int value, int l, int r) {

  int mid = 0; // Indexwert für (neue) Arraymitte

  while(r >= l) {
    mid = (r+l)/2; // mittlere Arrayposition errechnen (ganzzahlige Division!)

    if(value == a[mid]) { // wenn gleiches Element gefunden
      return mid+1; // dann Suche abbrechen und Einfügeposition zurückgeben
    } else if(value > a[mid]) { // wenn Element größer, als mittleres Element
      l = mid + 1; // dann im rechten schon sortierten Teilarray weitersuchen
    } else {
      r = mid - 1; // sonst im linken schon sortierten Teilarray weitersuchen
    }

  }

  return l;

}

Komplexität

binsearch() benötigt höchstens log2N + 1 Schleifendurchläufe (=Vergleiche). N steht hierbei für die Menge an Eingabedaten, hier Array-Elementen. Der Algorithmus liegt somit in der Komplexitätsklasse O(log n). Man spricht auch von logarithmischer Laufzeit.

Damit ist binsearch() deutlich effizienter als eine lineare Suche, die im worst case N Vergleiche benötigt und damit in der Komplexitätsklasse O(n) liegt.

» drucken: pdf | html

© 2004-2024 M. Blanke · Ursulaschule · Kleine Domsfreiheit 11-18 · 49074 Osnabrück