[AiSD] 1. Wyszukiwanie

#include <iostream>
#include <cstdlib>
#include <ctime>
using namespace std;

const int N = 20;
int tab[N]={};

void wypelnij()
{
    srand( time( NULL ) );
    for(int i = 0; i< N; i++)
        tab[i] = rand()%N;
}

void wypisz()
{
    for(int i = 0; i< N; i++)
        cout<<tab[i]<<" ";
    cout<<endl;
}

int wyszukiwanie_liniowe(int s)
{
    cout<<"[LINIOWE] ";
    int i = 0;
    while(i < N && tab[i] != s)
        i += 1;
    if(i >= N)
    {
        cout<<"Nie ma elementu: "<<s<<endl;
        return -1;
    }

    else
    {
        cout<<"Znaleziono element: "<<s<<endl;
        return i;
    }

}

int wyszukiwanie_binarne(int s)
{
    cout<<"[BINARNE] ";
    //tablica musi byc posortowana - zalozenie algorytmu
    for(int i= 0; i< N-1; i++)
        for(int j= 0; j< N-1; j++)
            if(tab[j]>tab[j+1])
                swap(tab[j], tab[j+1]);

    int lewy = 0;
    int prawy = N-1;
    bool znaleziono = false;
    while(lewy <= prawy && !znaleziono)
    {
        int srodek = (lewy+prawy)/2;
        if(tab[srodek] == s)
        {
            znaleziono = true;
            cout<<"Znaleziono element: "<<s<<endl;
            return srodek;
        }
        else
            if(s < tab[srodek])
                prawy = srodek-1;
            else
                lewy = srodek+1;
    }
    cout<<"Nie ma elementu: "<<s<<endl;
    return -1;
}

int wyszukiwanie_interpolacyjne(int s)
{
    cout<<"[INTERPOLACYJNE] ";
    //tablica musi byc posortowana - zalozenie algorytmu
    for(int i= 0; i< N-1; i++)
        for(int j= 0; j< N-1; j++)
            if(tab[j]>tab[j+1])
                swap(tab[j], tab[j+1]);

    int lewy = 0;
    int prawy = N-1;
    bool znaleziono = false;
    while(lewy <= prawy && !znaleziono)
    {
        int srodek = lewy + (s - tab[lewy])/(tab[prawy] - tab[lewy])*(prawy - lewy);
        if(tab[srodek] == s)
        {
            znaleziono = true;
            cout<<"Znaleziono element: "<<s<<endl;
            return srodek;
        }
        else
            if(s < tab[srodek])
                prawy = srodek-1;
            else
                lewy = srodek+1;
    }
    cout<<"Nie ma elementu: "<<s<<endl;
    return -1;
}

int main(){

    wypelnij();
    wypisz();
    wyszukiwanie_liniowe(5);
    wyszukiwanie_interpolacyjne(5);
    wyszukiwanie_binarne(5);
    return 0;
}