Datenstrukturen und Algorithmen

Eine Folge wird sequenziell durchsucht, beginnend mit dem ersten Element. In jedem Schritt wird das aktuelle Element mit dem Suchschlüssel verglichen. Wenn der Schlüssel gefunden wurde, wird beendet, sonst wird als Ergebnis \(NO \_KEY\) zurückgegeben.

\(\)Eingabe: Folge F der  Länge n, Suchschlüssel  k
Ausgabe: Position p des ersten Elementes aus F,  das  gleich k ist,  sonst NO_KEY

\(\textbf{for}\ i:= 1\ to \ n\ do \\ \ \ \ \ \ \ \ \ \textbf{if} \ F[i] = k\ \textbf{then}\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \textbf{return}\ i\\ \ \ \ \ \ \ \ \ \textbf{fi} \\ \textbf{od};\\ \textbf{return} \ NO \_ KEY \)

Ein Algorithmus ist eine eindeutige Beschreibung eines in mehreren Schritten durchgeführten (Bearbeitungs-)Vorganges.

Bester Fall: \(1\)
schlechtester Fall: \(n\)
Durchschnitt (erfolgreiche Suche): \( \frac{n + 1}{ 2 }\)
Durchschnitt (erfolglose Suche): \(n\)

Idee: Nutze Sortierung aus
Nutze „wahlfreien“ Zugriff auf beliebige Elemente
Prinzip: Wähle den mittleren Eintrag und prüfe, ob gesuchter Wert in der ersten oder in der zweiten Hälfte der Folge ist. Fahre rekursiv mit der Hälfte fort, in der sich der Eintrag befindet. 

Bester Fall: \(1\)
schlechtester Fall: \(\log_2n\)
Durchschnitt (erfolgreiche Suche): \(\log_2n\) 
Durchschnitt (erfolglose Suche): \(\log_2n\)

nach dem ersten Teilen der Folge: noch n/2 Elemente
nach dem zweiten Schritt: n/4 Elemente
nach dem dritten Schritt: n/8 Elemente

\(1 = \frac{n}{2^i} \rightarrow 2^i=n \rightarrow \log_2(2^i)=\log_2n \rightarrow i=\log_2n\)

• Datenstruktur mit beschränktem Zugriff
• 3 Methoden
• push: legt das Objekt als obersts Element auf dem Stack ab
• pop: nimmt das oberste Element vom Stack und gibt es zurück
• top (bzw. peek): gibt das oberste Element des Stacks zurück ohne es zu entfernen
• Außerdem: isEmpty: liefert true, wenn keine Element auf dem Stack liegen, andernfalls false