wyszukiwanie liniowym elementów w zbiorze oraz wyszukiwanie przez połowienie.

Question

Mam probem ze zrozumieniem tego tematu z wyszukiwaniem liniowym i przez połowienie czy ktoś mógł by mi pomóc z góry dziękuje
: )

Comments

Czy mógłbyś wyjaśnić bardziej szczegółowo z czym masz problem? Bo nawet nie wiem jakiej odpowiedzi oczekujesz i czy jestem w stanie pomóc

Answer 1

Wyszukiwanie liniowe jest proste. Jak chcesz w jakieś np. tablicy sprawdzic czy istnieje, to iterujesz się po wszystkich elementach i sprawdzasz czy jakiś pasuje. Jest ono bardzo proste w napisaniu i działa, ale jest wolne, bo sprawdzasz pesymistycznie każdy element, czyli ma O(N), gdzie N to liczba elementów w np. Tablicy.

Wyszukiwanie przez połowienie to binary serach (wyszukiwanie binarne), chodzi o to, że za każdym razem odzucasz połowę kandydatów i działa w O(log N). O samej implementacji bin searcha pisałem na forum w jednym z ostatnich wątków o bin searchu. Znajdź sobie, nie chce się powtarzać.