• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Wyszukiwanie binarne

Object Storage Arubacloud
+1 głos
398 wizyt
pytanie zadane 25 czerwca 2021 w Algorytmy przez Tanormalnie Użytkownik (550 p.)
Czy mogę użyć wyszukiwania binarnego na zbiorze liczb malejących?

1 odpowiedź

+2 głosów
odpowiedź 25 czerwca 2021 przez tkz Nałogowiec (42,000 p.)
wybrane 26 czerwca 2021 przez Tanormalnie
 
Najlepsza
Pewnie. Jedyna zasada, którą musisz spełnić, to by elementy były możliwe do porównania.
komentarz 26 czerwca 2021 przez adrian17 Ekspert (346,320 p.)
(raczej też ważne jest żeby ciąg był monotoniczny - po prostu mniej ważne, w którą stronę)
komentarz 26 czerwca 2021 przez tkz Nałogowiec (42,000 p.)
Czy ważne? Wątpię. Na pewno będzie lepiej pod względem wydajności, ale nie wpływa na poprawność.
komentarz 26 czerwca 2021 przez adrian17 Ekspert (346,320 p.)

ale nie wpływa na poprawność

https://pl.wikipedia.org/wiki/Wyszukiwanie_binarne

stwierdza, czy szukany element znajduje się w uporządkowanej tablicy

komentarz 26 czerwca 2021 przez tkz Nałogowiec (42,000 p.)
Mówisz o tablicy końcowej, na której już działamy. Myślałem o ogólnym zbiorze danych, które wchodzą do programu. Bez uprzedniego posortowania.
komentarz 26 czerwca 2021 przez adrian17 Ekspert (346,320 p.)
...mówię o wejściu do algorytmu wyszukiwania binarnego - o nie było pytanie. Dane muszą być posortowane.

Jeśli na pytanie "czy mogę użyć wyszukiwanie binarne na danych nieposortowanych" odpowiesz "tak, jeśli wcześniej je posortujesz" to tak naprawdę odpowiedź brzmi Nie.
komentarz 26 czerwca 2021 przez tkz Nałogowiec (42,000 p.)
No tak i napisałem "pewnie", że może użyć wyszukiwania binarnego na zbiorze liczb malejących. Dodałem, że najważniejszym warunkiem jest możliwość porównania elementów. Co implikuje na możliwość posortowania zbioru. Nie widzę, by była mowa o samym wejściu do samego algorytmu. Pytanie raczej było "luźne". By odpalić samochód musisz mieć kluczyk. Ważne, by też do niego wsiąść, co jest raczej oczywiste. Tak samo jak posortowane dane wejściowe.
komentarz 26 czerwca 2021 przez adrian17 Ekspert (346,320 p.)

Pytanie raczej było "luźne".

Nie widzę, by była mowa o samym wejściu do samego algorytmu

...przeczytaj jeszcze raz treść pytania. Zazwyczaj gdy pytanie brzmi "czy mogę użyć <algorytm> na <danych>" to implikuje bezpośrednie wejście do algorytmu.

Gdybyś na teście zobaczył pytanie "czy jedynym warunkiem algorytmu wyszukiwania jest binarnego jest, by elementy były możliwe do porównania" to Twoja odpowiedź "tak (bo sobie je wcześniej posortuje)" z definicji jest błędna i zaprzecza, że to jedyny warunek algorytmu.

Tak, można użyć algorytm na ciągu liczb malejących lub rosnących. Nie, nie można go bezpośrednio użyć na dowolnym zbiorze "porównywalnych liczb". Przygotowanie danych do algorytmu nie jest częścią tego algorytmu.

 

Podobne pytania

+1 głos
2 odpowiedzi 285 wizyt
pytanie zadane 23 września 2022 w Python przez doskanoness Obywatel (1,240 p.)
0 głosów
1 odpowiedź 1,493 wizyt
pytanie zadane 14 maja 2018 w Python przez ForeverFriendzone Dyskutant (7,520 p.)
0 głosów
0 odpowiedzi 420 wizyt

92,694 zapytań

141,606 odpowiedzi

320,106 komentarzy

62,051 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...