INF.03Programowanie
Wyszukiwanie liniowe vs Wyszukiwanie binarne
Dwa podstawowe algorytmy wyszukiwania elementów w kolekcji: liniowy O(n) dla dowolnych danych oraz binarne O(log n) dla tablic posortowanych.
Porównanie algorytmów wyszukiwania:
- Wyszukiwanie liniowe: Przegląda elementy jeden po drugim od początku do końca. Działa na tablicach nieposortowanych. Złożoność:
O(n). - Wyszukiwanie binarne: Działa wyłącznie na tablicach posortowanych. W każdym kroku porównuje szukaną wartość z elementem środkowym i odrzuca połowę przedziału (Dziel i zwyciężaj). Złożoność:
O(log n).
JAVASCRIPT
function wyszukiwanieBinarne(tabPosortowana, szukana) {
let lewy = 0;
let prawy = tabPosortowana.length - 1;
while (lewy <= prawy) {
let srodek = Math.floor((lewy + prawy) / 2);
if (tabPosortowana[srodek] === szukana) {
return srodek; // Znaleziono pod indeksem
} else if (tabPosortowana[srodek] < szukana) {
lewy = srodek + 1; // Szukaj w prawej połówce
} else {
prawy = srodek - 1; // Szukaj w lewej połówce
}
}
return -1; // Nie znaleziono
}Chcesz sprawdzić to pojęcie w praktyce?
Przeszukaj pytania z oficjalnych arkuszy CKE powiązane z hasłem Wyszukiwanie liniowe vs Wyszukiwanie binarne lub rozpocznij trening.