Sorting und Searching

Searching in unsorted array $\le O(n)$ Geht nicht besser. Jedes Element muss in einem Vergleich vorkommen $\ge \frac{n+1}{2}\ge \Omega (n)$ $/2$ because of the maximal optimistisum

Binary Search (Geht es besser)

Idee: Betrachte einen beliebigen Suche Algorithmus als Entscheidungsbaum Bsp: