# Portabilitaet: UNIVERSAL
# Zuletzt validiert: 2026-01-28 (Gemini)
# Naechste Pruefung: 2027-01-28
# Quellen: [informatik/algorithmen/README.txt]

SUCHALGORITHMEN
===============

Stand: 2026-01-28

UEBERBLICK
----------
Suche ist das Finden eines Elements innerhalb einer Datenstruktur. Die Wahl des Algorithmus haengt stark von der Struktur der Daten ab.

BASIS-SUCHVERFAHREN
-------------------

### Lineare Suche (Linear Search)
Prueft jedes Element der Reihe nach.
- **Komplexitaet:** O(n)
- **Voraussetzung:** Keine (Daten koennen unsortiert sein).
- **Einsatz:** Kleine Listen, unsortierte Daten.

### Binaere Suche (Binary Search)
Teile und herrsche. Springt in die Mitte. Ist der gesuchte Wert kleiner? Suche links weiter. Groesser? Suche rechts.
- **Komplexitaet:** O(log n)
- **Voraussetzung:** Daten MUESSEN sortiert sein.
- **Leistung:** Extrem schnell. Bei 4 Mrd. Eintraegen max. 32 Schritte.

GRAPHEN- & BAUMSUCHE
--------------------
Wenn Daten als Netzwerk (Graph) oder Hierarchie (Baum) vorliegen.

### Breitensuche (BFS - Breadth-First Search)
Erkundet erst alle Nachbarn, dann die Nachbarn der Nachbarn (schichtenweise).
- **Datenstruktur:** Queue (FIFO).
- **Einsatz:** "Kuerzester Weg" in ungewichteten Graphen (z.B. Facebook-Freunde-Distanz).

### Tiefensuche (DFS - Depth-First Search)
Geht einen Pfad so tief wie moeglich, bevor zurueckgegangen wird (Backtracking).
- **Datenstruktur:** Stack (LIFO) oder Rekursion.
- **Einsatz:** Labyrinthe loesen, Puzzle-Loesung finden, Topologische Sortierung.

SPEZIALISIERTE SUCHE
--------------------

### Hashing
Direkter Zugriff ueber einen Schluessel.
- **Komplexitaet:** O(1) im Durchschnitt.
- **Datenstruktur:** Hashmap / Dictionary.

### A* (A-Star)
Heuristische Suche. Erweitert Dijkstra (kuerzester Weg) um eine Schaetzung (Heuristik), wie weit das Ziel noch weg ist.
- **Einsatz:** Pathfinding in Spielen, Routenplanung (Google Maps).

VERGLEICHS-TABELLE
------------------
| Algorithmus | Datenstruktur | Zeit (Avg) | Besonderheit |
|-------------|---------------|------------|--------------|
| Linear | Liste | O(n) | Simpel |
| Binary | Sort. Array | O(log n) | Muss sortiert sein |
| Hashing | Hashmap | O(1) | Braucht Speicher |
| BFS | Graph | O(V+E) | Findet kuerzesten Weg |
| DFS | Graph | O(V+E) | Weniger Speicher als BFS |

SIEHE AUCH
----------
wiki/informatik/algorithmen/komplexitaet.txt
wiki/informatik/datenstrukturen/baeume.txt
