Jak używać wyszukiwania binarnego, aby sprawdzić, czy istnieje odległość między liczbami sąsiadów większymi niż N w posortowanej tablicy? Na przykład:
Input: 2 5 8 11 16
Distance: 4
Powinniśmy więc uzyskać odpowiedź, że istnieje taka odległość między sąsiadami. (między 11 a 16)
EDYCJA: Pozwól mi wyjaśnić, dlaczego chcę to zrobić za pomocą wyszukiwania binarnego.
Załóżmy, że tablica INPUT jest nieposortowana. Dawny:
Input: 11 8 2 16 5
Następnie należy posortować tablicę, aby zobaczyć, którzy są sąsiadami. Więc po tym, jak mamy posortowaną listę, czy nie jest to najlepszy sposób na znalezienie odległości z jakąś mutacją wyszukiwania binarnego?
Odpowiedzi:
0 dla odpowiedzi № 1Nie można użyć wyszukiwania binarnego w najgorszym przypadku, gdy wszystkie liczby są równo rozmieszczone N.
Ideą wyszukiwania binarnego i innych algorytmów dziel i zwyciężaj jest to, że eliminujesz mniej więcej połowę pozostałego zakresu na każdym kroku. Gdy wszystkie elementy są rozmieszczone w odstępach N, każdy zakres trzech lub więcej kolejnych przedmiotów może potencjalnie zawierać parę sąsiadów z odległością > N, więc nie można wyeliminować żadnego z dwóch rozważanych podzakresów. Ostatecznie zbadasz każdą parę kolejnych przedmiotów, co cię kosztuje O(NumItems).
Można jednak zoptymalizować ogólny przypadek, aby zrobić znacznie lepiej niż O(NumItems) z powodu potencjalnych możliwości przycinania.
0 dla odpowiedzi nr 2
Ty (cóż, ja) nie chciałbym: wyszukiwanie binarne wymaga posortowanej listy, a ty poświęcisz więcej czasu na sortowanie tej listy (par sąsiednich przedmiotów, uporządkowanych według ich odległości), niż po prostu skanowałbyś listę.