How to implement binary search in PHP? (code example)-PHP Tutorial-php.cn

How to implement binary search in PHP? (code example)

青灯夜游

Release： 2023-04-05 15:16:01

Original

2339 people have browsed it

Binary search (halving search) is a search technique used to search for elements in a sorted array. So how to implement binary search in PHP? The following article will introduce to you how to use iteration and recursion to implement binary search in PHP. I hope it will be helpful to you. [Video tutorial recommendation: PHP tutorial]

How to implement binary search in PHP? (code example)

##Method 1: Use iteration

Steps:

1. Sort the array, because binary search only works on sorted ranges

2. If the element we want to search is larger than the right If the middle element is searched, the middle element is calculated, otherwise the search on the left side is calculated.

3. If the element is found, True is returned.

Implementation code:

<?php 
header("content-type:text/html;charset=utf-8");
function binarySearch(Array $arr, $x) 
{ 
    // check for empty array 
    if (count($arr) === 0) return false; 
    $low = 0; 
    $high = count($arr) - 1; 
      
    while ($low <= $high) { 
          
        // 计算中间索引
        $mid = floor(($low + $high) / 2); 
   
        // 在中间找到元素
        if($arr[$mid] == $x) { 
            return true; 
        } 
  
        if ($x < $arr[$mid]) { 
            // 搜索数组的左侧
            $high = $mid -1; 
        } 
        else { 
            // 搜索数组的右侧
            $low = $mid + 1; 
        } 
    } 
      
    // 元素x不存在,返回false
    return false; 
} 
  
$arr = array(1, 2, 3, 4, 5); 
$value = 5; 
if(binarySearch($arr, $value) == true) { 
    echo "元素".$value."： 存在"; 
} 
else { 
    echo "元素".$value."： 不存在"; 
} 
?>

Copy after login

Output:

元素5： 存在

Copy after login

Method 2: Use recursion

Recursion is how we call the same function repeatedly until a basic condition is matched to end the recursion. The principle is the same as method one, just change the parameters of the function recursively and decompose the problem.

Implementation code:

<?php 
header("content-type:text/html;charset=utf-8");
function binarySearch(Array $arr, $start, $end, $x){ 
    if ($end < $start) 
        return false; 
   
    $mid = floor(($end + $start)/2); 
    if ($arr[$mid] == $x)  
        return true; 
  
    elseif ($arr[$mid] > $x) { 
  
        // 调用binarySearch()函数本身， 改变其中参数：$start, $mid-1
        return binarySearch($arr, $start, $mid - 1, $x); 
    } 
    else { 
  
        // 调用binarySearch()函数本身， 改变其中参数：mid + 1, end
        return binarySearch($arr, $mid + 1, $end, $x); 
    } 
} 
  
$arr = array(1, 2, 3, 4, 5); 
$value = 6; 
if(binarySearch($arr, 0, count($arr) - 1, $value) == true) { 
    echo "元素".$value."： 存在"; 
} 
else { 
    echo "元素".$value."： 不存在"; 
} 
?>

Copy after login

Output:

元素6： 不存在

Copy after login

The above is the entire content of this article, I hope it will be helpful to everyone's learning. For more exciting content, you can pay attention to the relevant tutorial columns of the PHP Chinese website! ! !

The above is the detailed content of How to implement binary search in PHP? (code example). For more information, please follow other related articles on the PHP Chinese website!