Wyszukiwanie binarne po wynikach cz III.

W poprzedniej części pokazaliśmy, że czasami łatwiej jest powiedzieć czy dana wartość spełnia warunki zadania, niż znaleźć najmniejszą z nich. W tej części przedstawię metodę, którą można rozwiązać wszystkie przedstawione w tej serii zadania. Przyjrzyjmy się najpierw jakie warunki musi spełniać zadanie, aby można było skorzystać z wyszukiwania binarnego po wynikach.

Aby móc skorzystać z opisanej poniżej metody, zadanie musi spełniać następujące warunki:

• Szukamy element e który:
• Spełnia warunki zadania
• Jest najmniejszym {największym} takim elementem
• Dla każdych elementów d oraz d' takich, że d < d' {d > d'} to jeśli d spełnia warunki zadania, to d' także

Drugi warunek może wydawać się dla niektórych skomplikowany. Dlatego rozpatrzymy go na przykładach:

Zadanie o krowach (d > d'). Jeśli potrafimy tak rozdzielić krowy, aby każda z nich była oddalona o conajmniej d jednostek od siebie, to potrafimy to też zrobić aby odległość między każdą z nich była większa o d' (wystarczy wybrać te same obory).

Zadanie o złodzieju (d > d'). Jeśli potrafimy tak wybrać przedmioty aby odpowiedni iloczyn był niemniejszy niż d, to potrafimy też tak je wybrać aby był niemniejszy od d' (wystarczy wybrać te same przedmioty).

Zadanie o zabytkach (d < d'). Jeśli potrafimy znaleźć po d dniach cykl w grafie, to potrafimy też znaleźć cykl po d' dniach (wystarczy "znaleźć" ten sam cykl).

Zatem drugi warunek mówi nam rzecz następującą. Podzielmy wszystkie elementy na dwa zbiory. W pierwszy zbiorze znajdą się wszystkie te liczby, które spełniają warunek zadania, a w drugim te które tego warunku nie spełniają. Każdy element w tym pierwszym zbiorze jest większy {mniejszy} niż każdy element w tym drugim. Prezentuje nam to poniższy rysunek:
Metoda wyszukiwania binarnego po wyniku przypomina zabawę w zgadywankę. Ja pomyślę o jakiejś liczbie. Ty będziesz zgadywał jaka to liczba, a ja będę mówił czy moja liczba jest większa czy mniejsza lub równa.

Pierwszym krokiem będzie znalezienie 2 elementów. Pierwszy z nich ma spełniać warunki zadania, a drugi nie. Oznaczmy je jako S_min oraz S_max.

Nasze rozwiązanie będzie znajdowało się gdzieś w środku (S_min, S_max). Policzmy średnią S_śr = (S_min + S_max) / 2. W zależności od tego czy S_śr spełnia czy nie spełnia warunków zadania, może zmniejszyć obszar naszych poszukiwań do (S_min, S_śr) lub (S_śr, S_max). Cały akapit powtarzamy dopóki nie będziemy pewni poprawnej odpowiedzi.

Istnieje wiele niepoprawnych algorytmów do zadań, które tu omówiliśmy. W następnej notce zaprezentuję kontrprzykłady do niektórych z nich.