PHP에서 이진 검색을 구현하는 방법은 무엇입니까? (코드 예)-PHP 튜토리얼-php.cn

PHP에서 이진 검색을 구현하는 방법은 무엇입니까? (코드 예)

青灯夜游

풀어 주다： 2023-04-05 15:16:01

원래의

2393명이 탐색했습니다.

이진 검색(또는 이진 검색)은 정렬된 배열에서 요소를 검색하는 데 사용되는 검색 기술입니다. 그렇다면 PHP에서 이진 검색을 구현하는 방법은 무엇입니까? 다음 기사에서는 PHP에서 이진 검색을 구현하기 위해 반복 및 재귀를 사용하는 방법을 소개합니다. 이것이 도움이 되기를 바랍니다. [동영상 튜토리얼 추천: PHP 튜토리얼]

PHP에서 이진 검색을 구현하는 방법은 무엇입니까? (코드 예)

방법 1: 반복 사용

단계:

1. 이진 검색은 정렬된 범위에서만 작동하므로 배열을 정렬합니다.

2. 검색하려는 요소가 오른쪽의 중간 요소 검색보다 크면 중간 요소를 계산하고, 그렇지 않으면 왼쪽의 검색을 계산합니다.

3. 요소가 발견되면 True를 반환합니다.

구현 코드:

<?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."： 不存在"; 
} 
?>

로그인 후 복사

출력:

元素5： 存在

로그인 후 복사

방법 2: 재귀 사용

재귀는 기본 조건이 일치하여 재귀를 종료할 때까지 동일한 함수를 반복적으로 호출하는 방식입니다. 원리는 방법 1과 동일합니다. 함수의 매개변수를 재귀적으로 변경하고 문제를 분해하면 됩니다.

구현 코드:

<?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."： 不存在"; 
} 
?>

로그인 후 복사

출력: