Chotkos's Blog

Programowanie i informatyka

Wyszukiwanie Binarne – Bisekcja

Dzisiaj poruszę temat wyszukiwania binarnego – o co chodzi?

Problem polega na tym, że mamy jakiś tam ciąg wartości w odpowiedniej kolejności – rosnącej lub malejącej – np. kolejkę w sklepie, w której mamy wózki w zależności od ilości zakupów w środku ustawione rosnąco, tak aby najpierw kupowali klienci którzy mają mało przedmiotów a więc szybciej przejdą w kolejce ( kto czekał kiedyś w markecie na przerwie chcąc kupić jedną bułkę i colę a przed nim jakaś starsza pani z toną przeróżnego śmiecia w koszyku ten wie, że jest to mocno wyidealizowana wizja). W każdym razie wchodzimy do takiego sklepu i pytamy „Gdzie stoi pani z zakupami za 100 złotych” Tutaj właśnie pojawia się problem szybkiego wyszukiwania.

Pierwszym sposobem jaki wpada do głowy jest oczywiście przejrzeć wszystkie wózki i w ten sposób znaleźć właściwy. Oczywiście świat zadań z programowania jest światem czarnych koszmarów więc możecie być pewni że kolejka ma ponad milion klientów, a ten właściwy wózek stoi gdzieś bardzo blisko końca. W tym wypadku złożoność n jest niedopuszczalna bo zależy nam bardzo na każdej setnej sekundy. Szukamy innej metody!

Zacznę trochę z innej beczki. Na początku państwa Rzymskiego Roma nie była wcale potęgą, dopiero mądra polityka umocniła ją w walce o supremację. Wtedy najważniejszą ideą była fraza „Divide at impera!” „Dziel i rządź” O ile starożytni wykorzystywali tą frazę do skłócania przeróżnych ludów i państw na własną korzyść, to w programowaniu wyrażenie to oznacza coś zdeka innego.

Pomyśl że naszą kolejkę dzielimy na dwa sektory od początku do połowy (środka) i od połowy (środka) do końca. Pytamy więc klienta stojącego w samym środku za ile zrobił zakupy

– jeżeli powie że za więcej niż 100 zł wtedy :

  1. koniec staje się środkiem // k:=s;
  2. Środek staje się środkiem między początkiem(p) a końcem // s:= (k-p) div 2 +1;

– Jeżeli powie że za mniej niż 100 zł wtedy:

  1. Początek staje się środkiem // p:=s;
  2. rodek staje się środkiem między początkiem(p) a końcem // s:= (k-p) div 2 +1;

-Jeżeli powie że za 100 zł wtedy

  1. p:=k;
  2. Koniec pętli. //break;

Właściwie to napisałem już cały program, wystarczy go tylko teraz przełożyć na jakiś język programowania a w nim zapętlić to co wypunktowałem.

Oczywiście możecie mi nie wierzyć, dlatego podam przykład, który mam nadzieję pomoże:

Szukamy klienta z zakupami za 2 złote. Oto lista wartości zakupów.

1 2 3 4 5 6 7 8 9 10 11 12 13

Pytamy (13-1) div 2 +1 = 6 klienta o to za ile zł ma zakupy. Okazuje się że za 6 złotych, więc idziemy w lewo.

1 2 3 4 5 6

Pytamy (6-1) div 2 +1 = 3 klienta o wartość zakupów, okazuje się że za 3 złote, więc znów idziemy w lewo.

1 2 3

Pytamy (3-1) div 2 +1 = 2 klienta o wartość zakupów , okazuje się że to ten który kupuje za 2 złote! Był drugi w kolejce!

Oczywiście mam kod, a nawet graficzne wytłumaczenie, wszystko w moim chomiku.

Reklamy

Styczeń 17, 2010 - Posted by | Algorytmy, Programowanie | ,

6 komentarzy »

  1. przydało by się opisać jeszcze jakieś szybkie sortowanie 🙂

    Komentarz - autor: DarkGL | Styczeń 17, 2010 | Odpowiedz

  2. mergesort będzie później, bo puki co to nie ogarniasz na zajęciach dgl a jak ja to powiem to niema opcji ;P

    Komentarz - autor: chotkos | Styczeń 17, 2010 | Odpowiedz

  3. widziałem kiedyś sortowanie w którym złożoność była O(+inf) 😀

    Komentarz - autor: DarkGL | Styczeń 17, 2010 | Odpowiedz

  4. nic lepszego niż mergesort nie zrozumiesz, a na pewno nie wymyślisz ;P

    Komentarz - autor: chotkos | Styczeń 18, 2010 | Odpowiedz

  5. Dobra robota ;]

    Komentarz - autor: lusiak | Styczeń 18, 2010 | Odpowiedz

  6. […] do bisekcji Artykuł o bisekcji był nieco wcześniej ale dzisiaj wrzuciłem zadanie – Kolejka. Ogólnie to nie mam niestety […]

    Pingback - autor: Zadanie do bisekcji « Chotkos's Blog | Styczeń 22, 2010 | Odpowiedz


Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s

%d blogerów lubi to: