Algorytm poszukiwanie przez połowienie

Specyfikacja:

Dane: Zbiór elementów w postaci ciągu n uporządkowanych liczb x1<= x2<= …<=xn. Wyróżniony element y. Wynik: Jeśli y należy do tego zbioru, podaj miejsce (index) w ciągu, w przeciwnym razie sygnalizuj brak takiego elementu w zbiorze.

Algorytm:

Powtarzaj kroki 1-3, dopóki nie natrafisz na poszukiwany element.

Krok 1: Sprawdź element środkowy ciągu (gdy ciąg ma nieparzystą liczbę elementów) lub jeden z dwóch elementów środkowych (gdy ciąg ma parzystą liczbę elementów).

Krok 2: Jeśli jest on elementem poszukiwanym y, to zakończ algorytm.

Krok 3: Jeśli środkowy element jest większy od y, to pozostaw podciąg na lewo od elementu środkowego, a w przeciwnym wypadku (gdy element środkowy jest mniejszy od y), pozostaw podciąg na prawo od elementu środkowego.

Zadanie: Zapisz program „Zgadnij jaka to liczba?” odpowiadający na podane pytanie.
Wybierz partnera z grupy. Następnie partner wymyśli dowolną liczbę n z przedziały [1, 50], a Ty masz ją znaleźć, zadając mu pytania typu: „Czy to jest liczba …?” Na co Twój partner może jedynie odpowiedzieć : „Tak”- gdy trafiłeś, lub „Za mała”, „Za duża”- w zależności od położenia wybranej przez Ciebie liczby względem ukrytej liczby.

Wytłumaczenie do tego algorytmu z forum elektroda:
Jak się szuka? Mamy przykładowo 32 liczby, od zera do 31
1.
zakresDolny = 0
zakresGorny = 31

2.
pozycja = w połowie = (zakresDolny+zakresGorny)/2

3.
Jeżeli tablica[pozycja] == szukana to znaleziono, exit.

Jeżeli liczba w tablicy na pozycji `pozycja` jest mniejsza od szukanej, to przesuwamy dolny zakres nad aktualną pozycję, bo szukanej liczby na pewno nie będzie niżej (zakresDolny=pozycja+1).

Jeżeli liczba w tablicy na pozycji `pozycja` jest większa od szukanej, to znaczy że jesteśmy za wysoko, więc górna granica spada poniżej aktualnej pozycji: zakresGorny=pozycja-1.

Jeżeli górny zakres nie jest większy od dolnego, powtórz od kroku 2.


Jeżeli nie znaleziono liczby, to automatycznie mamy pozycję na którą można wstawić nową liczbę (przesuwając wszystkie elementy po `prawej` w `prawo` o jedną pozycję). Jest nią pozycja+x, gdzie x jest jedynką tylko wtedy, gdy ostatnie porównanie podniosło dolną granicę.

Kod:
On: Pomyślałem sobie liczbą od zera do 31, zgadnij jaką? (pomyślał sobie 9)
Ja: (liczę...)
zakresDolny = 0
zakresGorny = 31
połowa = (zakresDolny+zakresGorny)/2 = 15

Ja: pytam czy to 15
On: mniej

Ja: (liczę... zostały liczby 0-14)
zakresDolny = 0
zakresGorny = 15-1 = 14
połowa = (0+14)/2 = 7

Ja: pytam czy to 7
On: więcej

Ja: (liczę... zostały liczby 8-14)
zakresDolny = 7+1 = 8
zakresGorny = 14
połowa = (8+14)/2 = 11

Ja: pytam czy to 11
On: mniej

Ja: (liczę... zostały liczby 8,9,10)
zakresDolny = 8
zakresGorny = 11-1 = 10
połowa = (8+10)/2 = 9

Ja: pytam czy to 9
On: Tak

Implementacja w C++

#include <iostream>

using namespace std;

const int n = 50;
const int y = 10;

int wyszukaj (int p, int k, int tab[])
{
int l_zbioru = k - p;
int polowa_liczb = l_zbioru/2;
int srodek_zbioru = p + polowa_liczb;



    if ( y == tab[srodek_zbioru]) return tab[y];
    if (l_zbioru < 0) return 0;

    if ( y < tab[srodek_zbioru]  )
        {
           return wyszukaj(p,srodek_zbioru-1,tab);

        }

    if ( y > tab[srodek_zbioru] )  return  wyszukaj (srodek_zbioru+1,k,tab);



}
int main()
{
    int tab[n];
    for (int i = 1; i<=n; i++)
    {
        tab[i] = i;

    }

    cout << wyszukaj(1,n,tab);
    return 0;
}