PHP finds whether an ordered array contains a certain value (binary search)

Question: For an ordered array, how to determine whether a given value exists in the array.

Idea: To determine whether it exists, the simplest way is to directly loop through the array and compare each value. But for ordered arrays, writing like this completely fails to take advantage of the "ordered" feature.

All we use "binary search",

//有序数组为
$arr = array(2,5,66,87,954,1452,5865);
//查找值
$str = 1452;
//我们先定义 三个参数
$front = 0;//一个开始值下标
$end = count($arr) - 1;//一个结束值下标
$mid = intval(($front + $end) / 2);//中间值下标

1. For the first comparison, we directly determine whether the search value str is equal to the intermediate value mid, and if it is equal, it returns true directly;

2. If the search value str is greater than the middle value mid, it means that the search value str may be to the right of the middle value, that is, the starting value front needs to be reassigned = the middle value mid 1, and the end value end does not need to be changed, and the middle value is sequentially mid is the new start value and end value;

3. If the search value str is less than the middle value mid, it means that the search value str may be to the left of the middle value, that is, the start value does not need to change, and the end value end needs to be reassigned. = middle value - 1, and the middle value mid is the start value and the new end value in turn;

-----As above, compare the incoming start value, end value, and middle value. Once the start value is greater than the end value, it means that it is not found and the query ends. Otherwise, it returns that it has been found.

The specific code is as follows:

$str = 89;//查找值
$arr = [1,55,66,89,420];//有序数组
$ren = find($arr, $str);
echo &#39;<pre class="brush:php;toolbar:false">&#39;;
var_dump($ren);
function find($arr, $str){
    $front = 0;//开始下标
    $end = count($arr) - 1;//结束下标
    while($front <= $end){//结束值 大于 开始值 ，反之则退出
        $mid = intval(($front + $end) / 2);//中间值下标
        if($str == $arr[$mid]){
            return $mid;//存在直接返回值的下标
        }
        if($str > $arr[$mid]){
            $front = $mid + 1;//在前面
        }
        if($str < $arr[$mid]){
            $end = $mid - 1;//在后面
        }
    }
    return false;
}

Return result: 89 is the fourth element value subscript 3

Recommended video tutorial: "php tutorial"

The above is the detailed content of PHP finds whether an ordered array contains a certain value (binary search). For more information, please follow other related articles on the PHP Chinese website!