Question

How to implement ternary search to find a value in a sorted list with PHP

Answer 1

function ternary_search(int $l, int $r, int $key, array $arr): int
{
    while ($l <= $r) {
        $mid1 = $l + intdiv(($r - $l), 3);
        $mid2 = $r - intdiv(($r - $l), 3);

        if ($arr[$mid1] === $key) {
            return $mid1;
        }

        if ($arr[$mid2] === $key) {
            return $mid2;
        }

        if ($key < $arr[$mid1]) {
            $r = $mid1 - 1;
        } elseif ($key > $arr[$mid2]) {
            $l = $mid2 + 1;
        } else {
            $l = $mid1 + 1;
            $r = $mid2 - 1;
        }
    }

    return -1; // not found
}

function main(): void
{
    $arr = [1, 2, 8, 14, 15, 64, 78, 89, 99, 100, 110, 123];
    $to_search = 89;

    $index = ternary_search(0, count($arr) - 1, $to_search, $arr);

    if ($index !== -1) {
        echo "Element found at index: $index\n";
    } else {
        echo "Element not found.\n";
    }
}

main();



/*
run:

Element found at index: 7

*/

 

70+ SQL courses for beginners and professionals