BinarySearch.php

BinarySearch.php

<?php
/**
 * Searching a value from a sorted array with dichotomy method.
 *
 * Keywords: median
 * Time Complexity: O(log n)
 * Space Complexity: O(1)
 *
 * @param int $target The value you want to find.
 * @param array $sorted_array The sorted array you want to search.
 * @return int
 */
function BinarySearch($target, $sorted_array)
{
    $head = 0;
    $tail = count($sorted_array) - 1;
    while (true) {
        // Get the middle value.
        $mid = (int)floor(($head + $tail) / 2);
        $value = $sorted_array[$mid];
        // Get the target
        if ($value == $target) {
            return $mid;
        }
        // Reset head or tail.
        if ($value > $target) {
            $tail = $mid;
        } else {
            $head = $mid;
        }
    }
}
# Example.
$sorted_array = [1,2,4,5,7,9,12,20];
$target = 5;
echo 'sorted array : ', PHP_EOL;
print_r($sorted_array);
echo 'target : ', $target, PHP_EOL;
echo 'result : ', BinarySearch($target, $sorted_array), PHP_EOL;
# end of this file.