Algorithms snippets

binary_search.php

<?php

function binary_search($array, $value) {
    $upper = count($array) -1;
    $lower = 0;

    while ($lower <= $upper) {
        $mid = floor(($lower + $upper) / 2);
        if ($array[$mid] == $value) {
            return $mid;
        } elseif ($array[$idx] > $value) {
            $upper = $mid - 1;
        } else {
            $lower = $mid + 1;
        }
    }
    return -1;
}

$array = array(1,2,3,4,5,6,7,8,9);

echo binary_search($array, 5); # => 4

bubble_sort.php

<?php

function bubble_sort($array) {
    $length = count($array);

    $sorted = false;
    while($sorted === false) {
        $sorted = true;
        for ($i=1; $i<$length; $i++) {
            if ($array[$i-1] > $array[$i]) {
                list($array[$i-1], $array[$i]) = array($array[$i], $array[$i-1]);
                $sorted = false;
            }
        }
    }
    return $array;
}

$unsorted = array(43,21,2,1,9,24,2,99,23,8,7,114,92,5);
print_r(bubble_sort($unsorted));

fibonacci.php

<?php
// fibonacci numbers
function fibonacci($n) {
    if ($n < 2) {
        return $n;
    }

    //return fibonacci($n-1) + fibonacci($n-2);

    $a1 = 0; $a2 = 1;
    for ($i=1; $i<$n; $i++) {
        $next = $a1 + $a2;
        $a1 = $a2;
        $a2 = $next;
    }

    return $next;
}

echo fibonacci(3);

quick_sort.php

<?php

function quick_sort($array) {
    $length = count($array);
    if ($length <= 1) {
        return $array;
    } else {
        $pivot = $array[0];
        $left = $right = array();
        for ($i = 1; $i < $length; $i++) {
            if ($array[$i] < $pivot) {
                $left[] = $array[$i];
            } else {
                $right[] = $array[$i];
            }
        }
        return array_merge(quick_sort($left), array($pivot), quick_sort($right));
    }
}


$unsorted = array(43,21,2,1,9,24,2,99,23,8,7,114,92,5);
print_r(quick_sort($unsorted));