PHP에서 구현된 이진 검색 알고리즘에 대한 예제 설명

이 글에서는 주로 PHP에서 구현되는 반탐색 알고리즘을 소개하고, 반탐색의 원리를 간략하게 설명하고, 반탐색 알고리즘을 구현하기 위한 재귀적 방법과 비재귀적 방법을 사용하여 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

관심을 가질 만한 기사:

PHP에서 구현된 문자열 일치 알고리즘의 예

PHP 구현된 최대 순방향 일치 알고리즘의 예

PHP 성능 분석 도구 xhprof의 설치 및 사용과 관련 주의 사항

위 내용은 PHP에서 구현된 이진 검색 알고리즘에 대한 예제 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!