How to implement binary search algorithm using PHP

How to use PHP to implement the binary search algorithm

The binary search algorithm is an efficient search algorithm suitable for finding specified elements in an ordered array. This article will introduce how to use PHP language to implement the binary search algorithm, and attach code examples.

The idea of ​​the binary search algorithm is to divide the array into two parts, and then determine which part the target value is in by comparing the size relationship between the target value and the middle element. If the middle element is equal to the target value, the search is successful; otherwise, based on the size relationship between the middle element and the target value, continue searching in the corresponding part until the target value is found or it is determined that the target value does not exist.

The following is a code example for PHP to implement the binary search algorithm:

function binary_search($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;
    
    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);
        
        if ($arr[$mid] == $target) {
            return $mid;
        }
        
        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }
    
    // 目标值不存在
    return -1;
}

$arr = [1, 3, 5, 7, 9, 11, 13, 15];
$target = 7;
$result = binary_search($arr, $target);

if ($result == -1) {
    echo "目标值不存在";
} else {
    echo "目标值在数组中的位置是：" . $result;
}

Run the above code, the output will be "The position of the target value in the array is: 3", indicating that the target value 7 is in the array The index position in is 3.

The binary_search function in the above code receives two parameters: the ordered array to be searched and the target value. The function uses two pointers left and right to represent the search range of the array. Continuously narrow the search range through the while loop until the target value is found or it is determined that the target value does not exist.

The key in the code is to calculate the index position of the middle element through the $mid variable, and then compare it with the target value. If they are equal, the index position is returned, otherwise the search range is adjusted according to the size relationship and the next round of binary search is continued.

It should be noted that the binary search algorithm requires an ordered array as input, otherwise it cannot be searched correctly. Therefore, before using the binary search algorithm, you must ensure that the array to be searched has been sorted in ascending (or descending) order.

The time complexity of the binary search algorithm is O(logn), which is more efficient than the O(n) of the linear search algorithm. When processing large-scale data, using the binary search algorithm can significantly improve search efficiency.

I hope this article can help readers understand and master the method of using PHP language to implement the binary search algorithm. By rationally using the binary search algorithm, we can perform search operations in ordered arrays more efficiently.

The above is the detailed content of How to implement binary search algorithm using PHP. For more information, please follow other related articles on the PHP Chinese website!