<?php

/**
 * Zoekt met binary search een getal op in een lijst getallen.
 *
 * @param array   $list  De zoekarray (met getallen)
 * @param int     $value De te zoeken waarde
 * @param int     $left  De ondergrens (index) van het te zoeken stuk in de array
 * @param int     $right  De bovengrens (index) van het te zoeken stuk in de array
 * 
 * @return de index van het element dat overeenkomt met $value, of -1 als $value 
 *         niet voorkomt in $list
 * @throws Exception "index out of bounds" als ingevoerde grenzen fout zijn
 * @author Uitgeverij Instruct
 * 
 */ 
function binary_search(array &$list, int $value, int $left = 0, int $right = -1) : int {
    
    //Controleer de invoer
    $size = count($list);
    if($right === -1) { 
        $right = $size - 1; 
    }
    
    if($left < 0 || $right >= $size || $left > $right) {
        throw new Exception("index out of bounds");
    }
    
    // Als de te controleren deellijst max 2 elementen bevat
    // Dan handmatig controleren
    if(($right - $left) < 2) {
        if($list[$left] === $value) return $left;
        if($list[$right] === $value) return $right;
        return -1;
    }
    
    //Bereken de middelste index van de deellijst en controleer 
    //of $value voorkomt op die plaats
    $center = floor(($left + $right) / 2);
    if($list[$center] === $value) return $center;
    
    //Voer binary_search uit op de linkerhelft
    //En controleer of dat een resultaat heeft opgeleverd
    $result = binary_search($list, $value, $left, $center);
    if($result > -1) return $result;
    
    //Voer binary_search uit op de rechterhelft
    //Return het resultaat
    return binary_search($list, $value, $center, $right);
}

//Test: zoek 23 en 21 op in $list1
$list1 = array(2, 3, 5, 7, 9, 23, 57, 99);
echo binary_search($list1, 23) . "\n";
echo binary_search($list1, 21);