Rozwiąż quiz: Algorytm wyszukiwania binarnego | Zestly

Question 1

Jaki jest podstawowy warunek wstępny, który musi zostać spełniony, aby algorytm wyszukiwania binarnego mógł poprawnie odnaleźć element w tablicy?

Accepted Answer

Elementy w tablicy muszą być uporządkowane niemalejąco lub nierosnąco

Answer

Tablica musi zawierać wyłącznie liczby całkowite

Answer

Tablica musi mieć parzystą liczbę elementów

Answer

Wartości w tablicy muszą być unikalne

Question 2

Wybierz poprawne stwierdzenia dotyczące złożoności obliczeniowej algorytmu wyszukiwania binarnego.

Accepted Answer

Złożoność w pesymistycznym przypadku wynosi $O(\log n)$

Accepted Answer

Algorytm jest znacznie szybszy od wyszukiwania liniowego dla dużych zbiorów danych

Answer

Złożoność zależy liniowo od liczby elementów $O(n)$

Answer

Złożoność wynosi $O(n^2)$ dla posortowanych tablic

Question 3

Które z poniższych operacji są wykonywane wewnątrz pojedynczego kroku algorytmu wyszukiwania binarnego?

Accepted Answer

Wyznaczenie indeksu środkowego przedziału

Accepted Answer

Porównanie wartości szukanej z wartością pod indeksem środkowym

Answer

Sortowanie tablicy w celu przygotowania do kolejnego kroku

Answer

Dodanie nowego elementu do tablicy

Question 4

Jeśli w trakcie wyszukiwania binarnego szukana wartość jest mniejsza od wartości w środkowym indeksie tablicy, co powinien zrobić algorytm?

Answer

Zakończyć działanie i zwrócić błąd

Answer

Kontynuować poszukiwania w lewej połowie tablicy

Answer

Kontynuować poszukiwania w prawej połowie tablicy

Answer

Zwiększyć zakres poszukiwań o jeden element

Question 5

Dlaczego wyszukiwanie binarne nie jest stosowane w listach wiązanych (linked lists)?

Answer

Brak dostępu swobodnego (random access) do elementów

Answer

Listy wiązane są zawsze posortowane

Answer

Algorytm ten działa tylko na tablicach dwuwymiarowych

Answer

Listy wiązane są zbyt krótkie