PHP 반검색 알고리즘 사례에 대한 자세한 설명

이번에는 PHP 반검색 알고리즘 사례에 대해 자세히 설명하겠습니다. PHP 반검색 사용 시 주의사항은 무엇인가요? 실제 사례를 살펴보겠습니다.

소개:

이진 검색 기술은 절반 검색이라고도 알려져 있습니다. 그 전제는 선형 테이블의 레코드가 키 순서(일반적으로 작은 것에서 큰 순서)로 되어 있어야 하고 선형 테이블이 순차적으로 저장되어야 한다는 것입니다.

기본 아이디어:

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

코드:

<?php
//二分搜索(折半查找)算法(前提是数组必须是有序数组) 时间复杂度是 O(logn)
$i = 0; //存储对比的次数
//@param 待查找数组
//@param 待搜索的数字
function binsearch($arr,$num){
 $count = count($arr);
 $lower = 0;
 $high = $count - 1;
 global $i;
 while($lower <= $high){
  $i ++; //计数器
  if($arr[$lower] == $num){
   return $lower;
  }
  if($arr[$high] == $num){
   return $high;
  }
  $middle = intval(($lower + $high) / 2);
  if($num < $arr[$middle]){
   $high = $middle - 1;
  }else if($num > $arr[$middle]){
   $lower = $middle + 1;
  }else{
   return $middle;
  }
 }
 //返回-1表示查找失败
 return -1;
}
$arr = array(0,1,16,24,35,47,59,62,73,88,99);
$pos = binsearch($arr,62);
print($pos);
echo "<br>";
echo $i;

실행 결과:

7
3

요약:

이진 검색의 시간 복잡도는 O(logn)입니다. 그러나 이진 검색의 전제 조건은 정렬된 테이블(배열)을 순차적으로 저장하는 것이므로 정렬된 테이블에 빈번한 삽입 또는 삭제 작업이 필요한 경우 정렬된 정렬을 유지하면 상당한 작업 부하가 발생하게 됩니다.

이 기사의 사례를 읽은 후 방법을 마스터했다고 생각합니다. 더 흥미로운 정보를 보려면 PHP 중국어 웹사이트의 다른 관련 기사를 주목하세요!

추천 도서:

PHP 긴 연결 사용 사례 분석

PHP 애플리케이션 컨테이너화 및 배포 사용에 대한 자세한 설명

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