Cwiczenie 12

/* Cwiczenie 12 */

#include <stdio.h>
#include <assert.h>

typedef unsigned int uint;

void szukajBinarnie(uint posortowana[], uint rozmiar, uint szukana) {
    /* ************* Algorytm poszukiwania binarnego *************  */
    /* Mamy posortowana tablice. Aby szukac w niej wartosci mozemy  */
    /* zastosowac nastepujaca procedure:                            */
    /*   1. Porownujemy szukana wartosc z elementem srodkowym       */
    /*      tablicy. Jezeli szukana jest mniejsza niz element, to   */
    /*      wiemy, ze nie znajdziemy szukanej w prawej czesci       */
    /*      tablicy. 'Idziemy' wiec w lewo.                         */
    /*   2. Podobnie, jezeli szukana jest wieksza niz element, to   */
    /*      'idziemy' w prawo.                                      */
    /*   3. W koncu, jezeli szukana jest rowna elementowi, to       */
    /*      znalezlismy poszukiwana wartosc!                        */
    /* Postepujac w ten sposob zawsze odnajdziemy szukana wartosc   */
    /* pod warunkiem, ze jest w tablicy. Jezeli wartosci nie ma     */
    /* w tablicy, to mozemy to wykryc badajac indeks poczatku i     */
    /* konca. Jezeli poczatek > koniec to nie ma juz gdzie szukac   */
    /* Zatem wartosci nie ma w tablicy.                             */
    /* ************************************************************ */

    uint poczatek = 0;          /* indeks poczatku */
    uint koniec   = rozmiar-1;  /* indeks konca    */
    uint srodek;                /* indeks srodka   */



    assert(rozmiar > 0);

    while ( !(poczatek > koniec) ) {
        srodek = (koniec+poczatek)/2;
        if (szukana < posortowana[srodek])
            koniec = srodek-1;    /* idziemy na lewo  */
        else if (szukana > posortowana[srodek])
            poczatek = srodek+1;  /* idziemy na prawo */
        else {
            printf("Znaleziono %u na miejscu %u!!!1\n", szukana, srodek);
            return; /* Wychodzimy z funkcji */
        }
    }

    printf("Nie znaleziono %u w tablicy. :(\n", szukana);
}

int main(int argc, char* argv[]) {
    uint tab[] = {1,3,4,5,6,7,9,11};
    uint rozmiar = sizeof(tab)/sizeof(*tab);

    szukajBinarnie(tab, rozmiar, 3);

    return 0;
}