Uses a binary search tree algorithm to locate a value in the specified array.

BinarySearchTreeArray.php

<?php

/**
 * Uses a binary search algorithm to locate a value in the specified array
 * Due to internal function call overhead (count, floor), it might be inefficient to use on small arrays
 *
 * Original:
 * @author Nicholas C. Zakas
 * @see https://www.htmlgoodies.com/beyond/javascript/how-to-search-a-javascript-string-array-using-a-binary-search.html
 *
 * PHP port by:
 * @author Aleksandar Puharic <[email protected]>
 * @see https://github.com/xZero707
 *
 * @param array $items Array to search in
 * @param string|int $value The value to search for
 *
 * @return int The zero-based index of the value in the array or -1 if not found
 *
 * Note: Return value might be 0 which evaluates to false, but is correct array index
 *
 * Use following for in_array behaviour
 * (bool)(binarySearch($animalsArray, 'Zebra') >= 0)
 */
function binarySearch(array $items, $value): int
{
    $startIndex = 0;
    $stopIndex  = count($items) - 1;
    $middle     = (int)floor(($stopIndex + $startIndex) / 2); // Casting is required since floor returns float

    while ($items[$middle] !== $value && $startIndex < $stopIndex) {

        //adjust search area
        if ($value < $items[$middle]) {
            $stopIndex = $middle - 1;
        } else if ($value > $items[$middle]) {
            $startIndex = $middle + 1;
        }

        //recalculate middle
        $middle = (int)floor(($stopIndex + $startIndex) / 2); // Casting is required since floor returns float
    }

    //make sure it's the right value
    return ($items[$middle] !== $value) ? -1 : $middle;
}