#! /usr/bin/perl

#Szukanie elementu w tablicy metoda bisekcji (metoda polowkowa)
#Dominik Gozdziuk
#www.algorytm.org

#Procedura sortujaca tablice podana jako parametr
sub sort {
        for ($i = 0; $i <= $#_; $i++) {
                $min = $i;
                for ($j = $i+1; $j <= $#_; $j++) {
                        if ($_[$j] < $_[$min]) {
                                $min = $j;
                        }
                }
                $tmp = $_[$i];
                $_[$i] = $_[$min];
                $_[$min] = $tmp;
        }
}

@tab = (45,24,56,43,78,67,25,7,58,95,69,49,32);

#Wywolanie procedury sort
&sort(@tab);

print "Tablica posortowana: ";
#Wyswietlenie tablicy
foreach $zmienna (@tab) {
        print "$zmienna ";
}

#Pobranie szukanego elementu
print "\nWprowadz szukany element: ";
$szukana = <STDIN>;
chomp($szukana);


$p = 0; #indeks pierwszego elementu tablicy
$k = $#tab; #indeks ostatniego elementu tablicy
$ok = 0; #zmienna pomocnicza

while ($p <= $k) {
        $s = ($p+$k)/2;
        $s = int($s); # Wyciagamy czesc calkowita

        if ($tab[$s] == $szukana) {
                $ok = 1;
                $p = $k+1; #Zmieniamy p aby zakonczyc petle
        }
        elsif ($tab[$s] > $szukana) {
                #Szukana jest mniejsza, zawezamy obszar poszukiwan
                $k = $s-1; #Zmieniamy k
        }
        else {
                # Szukana jest wieksza
                $p = $s+1; #Zmieniamy p
        }
}

#Wyswietlamy wynik
if ($ok == 1) {
        print "\nSzukany element znajduje sie w tablicy\n";
}
else {
        print "\nSzukany element nie znajduje sie w tablicy\n";
}