PHP에서 이진 검색 알고리즘을 구현하는 방법-PHP 튜토리얼-php.cn

PHP에서 이진 검색 알고리즘을 구현하는 방법

小云云

풀어 주다： 2023-03-18 06:16:01

원래의

2143명이 탐색했습니다.

이 글에서는 주로 PHP에서 구현되는 반탐색 알고리즘을 소개하고, 반탐색의 원리를 간략하게 설명하고, 반탐색 알고리즘을 구현하기 위한 재귀적 방법과 비재귀적 방법을 사용하여 PHP의 관련 조작 기술을 분석하여 예제 형태로 보여줍니다. . 필요한 친구들이 참고하면 도움이 될 것 같아요.

정의: 반검색 기술, 즉 이진 검색입니다. 그 전제는 선형 테이블의 레코드가 키 순서(보통 큰 것에서 작은 것)로 되어 있어야 하고 선형 테이블이 순차적으로 저장되어야 한다는 것입니다.

절반 검색의 기본 아이디어: 중간 레코드를 비교 대상으로 사용합니다. 주어진 값이 중간 레코드의 키워드와 같으면 지정된 값보다 작으면 검색이 성공합니다. 중간 레코드의 값이 검색에 성공하면 검색을 계속합니다. 주어진 값이 중간 레코드의 키보다 크면 중간 레코드의 오른쪽 절반에서 검색을 계속합니다. 검색이 성공할 때까지 또는 모든 검색 영역에 기록이 없어 검색이 실패할 때까지 위의 과정을 반복합니다.

구현 코드:

<?php
//递归方式
function bin_recur_search($arr,$val){
  global $time;
  if(count($arr) >= 1){
    $mid = intval(count($arr) / 2);
    $time++;
    if($arr[$mid] == $val){
      return &#39;值为:&#39;.$arr[$mid].&#39;<br>查找次数：&#39;.$time.&#39;<br>&#39;;
    }elseif($arr[$mid] > $val){
      $arr = array_splice($arr,0,$mid);
      return bin_recur_search($arr, $val);
    }else{
      $arr = array_slice($arr,$mid + 1);
      return bin_recur_search($arr, $val);
    }
  }
  return &#39;未找到&#39;.$val;
}
//非递归方式
function bin_search($arr,$val){
  if(count($arr) >= 1){
    $low = 0;
    $high = count($arr);
    $time = 0;
    while($low <= $high){
      $time++;
      $mid = intval(($low + $high)/2);
      if($val == $arr[$mid]){
        return &#39;索引：&#39;.$mid.&#39;<br>值为：&#39;.$arr[$mid].&#39;<br>查找次数：&#39;.$time;
      }elseif($val > $arr[$mid]){
        $low = $mid + 1;
      }else{
        $high = $mid - 1;
      }
    }
  }
  return &#39;未找到&#39;.$val;
}
$arr = array(1,3,5,7,7,9,25,68,98,145,673,8542);
echo bin_recur_search($arr, 673);
echo bin_search($arr, 673);
?>

로그인 후 복사

실행 결과:

值为:673
查找次数：4
索引：10
值为：673
查找次数：4

로그인 후 복사