Binary search

O(log n)

Binární vyhledávání potřebuje seřazené pole. Zkontroluje prostřední prvek: když se rovná hledané hodnotě, hotovo; když je hledaná hodnota menší, ponecháš levou půlku, jinak pravou — prostor půlíš každý krok. To dává O(log n), ale jen díky seřazení (tady se nejdřív seřadí).

Pole
Uprav vstup a stiskni Přehrát

Jak to funguje

  1. Podívej se na prostřední prvek aktuálního rozsahu.
  2. Když se rovná hledané hodnotě, hotovo.
  3. Když je hledaná hodnota menší, ponech levou půlku; když větší, pravou.
  4. Opakuj na zbylé půlce, dokud není rozsah prázdný.

Pseudokód

1binarySearch(a, target):            # O(log n) — a is sorted2  lo ← 0; hi ← n-13  while lo ≤ hi:4    mid ← (lo + hi) / 25    if a[mid] = target: return mid6    if a[mid] < target: lo ← mid+17    else: hi ← mid-18  return -1