Dlaczego wyszukiwanie binarne, które wymaga posortowanych danych, uważa się za lepsze niż wyszukiwanie liniowe?

Zawsze słyszałem, że wyszukiwanie liniowe jest naiwnym podejściem, a wyszukiwanie binarne jest lepsze niż pod względem wydajności ze względu na lepszą asymptotyczną złożoność. Ale nigdy nie zrozumiałem, dlaczego jest lepsze niż wyszukiwanie liniowe, gdy przed wyszukiwaniem binarnym wymagane jest sortowanie?

Wyszukiwanie liniowe jest, O(n)a wyszukiwanie binarne O(log n). To wydaje się być podstawą do stwierdzenia, że ​​wyszukiwanie binarne jest lepsze. Ale wyszukiwanie binarne wymaga sortowania, które jest O(n log n)najlepsze algorytmy. Wyszukiwanie binarne nie powinno być w rzeczywistości szybsze, ponieważ wymaga sortowania.

Czytam CLRS, w którym autor sugeruje, że w sortowaniu wstawiania zamiast naiwnego wyszukiwania liniowego lepiej jest użyć wyszukiwania binarnego w celu znalezienia miejsca, w którym element musi zostać wstawiony. W tym przypadku wydaje się to uzasadnione, ponieważ przy każdej iteracji pętli istnieje posortowana lista, na której można zastosować wyszukiwanie binarne. Ale w ogólnym przypadku, gdy nie ma gwarancji, że zestaw danych, w którym musimy szukać, nie używa wyszukiwania binarnego w rzeczywistości gorszego niż wyszukiwanie liniowe ze względu na wymagania dotyczące sortowania?

Czy pomijam jakieś względy praktyczne, które sprawiają, że wyszukiwanie binarne jest lepsze niż wyszukiwanie liniowe? Czy wyszukiwanie binarne jest uważane za lepsze niż wyszukiwanie liniowe bez uwzględnienia czasu obliczeń wymaganego do sortowania?

Czy pomijam jakieś względy praktyczne, które sprawiają, że wyszukiwanie binarne jest lepsze niż wyszukiwanie liniowe?

Tak - musisz wykonać sortowanie O (n log n) tylko raz, a następnie możesz wyszukiwać binarnie O (log n) tak często, jak chcesz, podczas gdy wyszukiwanie liniowe to O (n) za każdym razem.

Oczywiście jest to tylko zaleta, jeśli faktycznie przeprowadzasz wielokrotne wyszukiwania tych samych danych. Ale scenariusze „pisz raz, czytaj często” są dość powszechne.

Podstawowym założeniem jest to, że nie przeprowadzasz jednego wyszukiwania.

Jeśli więc musisz wielokrotnie przeszukiwać te same dane, musisz tylko raz posortować dane i skorzystać z wyszukiwania binarnego.

Jeśli często wyszukujesz i zmieniasz dane, warto skorzystać z posortowanej listy, w której nowe wpisy są sortowane na liście.

Zasadniczo wyszukiwanie binarne jest lepsze, gdy przeszukujesz tę samą listę wiele razy bez potrzeby uciekania się.

Kiedy za każdym razem musisz sortować przed wyszukiwaniem, nie ma żadnej przewagi.

Zauważmy, że istnieją algorytmy sortowania, które są bardzo szybkie, gdy lista jest już posortowana (lub prawie posortowana). Większość ustaleń dotyczących wydajności oczekuje nieposortowanej listy.

ponieważ gdy masz już posortowaną listę, nie musisz jej ponownie sortować za każdym razem, co oznacza, że ​​jeśli masz więcej niż O (log n) wyszukiwań z wyprzedzeniem, sortowanie z wyprzedzeniem zapewni Ci wygraną (w O(n log n + k log n)porównaniu zO(k*n)

Wyobraź sobie dwie książki telefoniczne.

Jedna książka telefoniczna ma nazwy w kolejności alfabetycznej. Aby znaleźć żądany wpis, otwórz go w środku, sprawdź wpis, a następnie przejdź do przodu lub do tyłu w zależności od tego, czy został przekroczony, czy cofnięty.

Druga książka telefoniczna ma nazwy w losowej kolejności. Aby znaleźć odpowiedni wpis, zacznij od początku i kontynuuj, aż znajdziesz to, czego szukasz.

Czy druga książka będzie działać w jakimkolwiek rozsądnym mieście?

Myślę, że wartość wyszukiwania binarnego nad wyszukiwaniem liniowym jest kontekstowa. Jeśli zaczniesz od ogromnego, nieuporządkowanego zestawu danych i planujesz jedynie wyciągnąć z niego niewielką liczbę elementów, sortowanie i wyszukiwanie binarne będzie powolne. Jeśli jednak utrzymujesz uporządkowaną listę przez cały okres użytkowania aplikacji i regularnie uzyskujesz do niej dostęp, wyszukiwanie binarne jest znacznie lepszym sposobem.

Podobnie jak wiele innych osób odpowiedziało, wyszukiwanie binarne jest rzeczywiście preferowane, ponieważ krok sortowania można wykonać tylko raz, a wyszukiwanie można wykonać tyle razy, ile chcesz. Jednak w przypadku niektórych wartości n (tj. Niektórych rozmiarów wejściowych) wyszukiwanie binarne jest zawsze bardziej wydajne niż wyszukiwanie liniowe (nawet dla pojedynczego przebiegu).

„Punkt krytyczny” oblicza się, rozwiązując asymptotyczne równanie złożoności:

n log n + log n = n

Jak widać na Wolfram Alpha, istnieje wartość liczbowa dla n, która zapewnia, że ​​wyszukiwanie i sortowanie binarne jest zawsze szybsze niż samo wyszukiwanie liniowe. Oczywiście rzeczywista wartość n, która działa w twoim przypadku, zależy od wielu czynników, które mogą być trudne do oszacowania.

Według tego interesującego artykułu Marka Probsta, który zawiera kilka ciekawych pomiarów wydajności obecnych procesorów:

Jeśli potrzebujesz przeszukać uporządkowaną tablicę liczb całkowitych, a wydajność jest naprawdę bardzo ważna, użyj wyszukiwania liniowego, jeśli tablica ma mniej więcej około 64 elementów, a wyszukiwania binarnego, jeśli jest powyżej.

Słowami laika:

Jeśli masz nieuporządkowaną listę z dziesięcioma miliardami pozycji, a pozycja, której szukasz, jest ostatnią, skończysz czytać dziesięć miliardów pozycji.

W przypadku wyszukiwania binarnego indeksowanie można wykonać tylko raz. Późniejsze wstawki można wykonać w odpowiednim miejscu, aby zachować porządek.

Chociaż wymieniono już wiele dobrych powodów, dla których „wyszukiwanie binarne jest lepsze”, możemy również spojrzeć na zalety z perspektywy użytkownika:

Chociaż normalnie możesz żyć bardzo dobrze z niewielkim czasem oczekiwania między operacjami wprowadzania danych podczas sortowania wstawki, chcesz, aby „wyszukiwanie” było tak szybkie, jak to możliwe. Z punktu widzenia użytkownika posortowana wstawka w połączeniu z wyszukiwaniem binarnym zapewnia najlepszą możliwą obsługę.