집 > 기사 > 백엔드 개발 > PHP 정렬 목록 이진 검색(반 검색) 알고리즘 공유

PHP 정렬 목록 이진 검색(반 검색) 알고리즘 공유

小云云원래의: 2018-02-11 09:06:191787검색

이 글에서는 주로 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( 로그인) . 그러나 이진 검색의 전제 조건은 정렬된 테이블(배열)을 순차적으로 저장하는 것이므로 정렬된 테이블에 빈번한 삽입 또는 삭제 작업이 필요한 경우 정렬된 정렬을 유지하면 상당한 작업 부하가 발생하게 됩니다.

PHP 정렬 목록 이진 검색(반 검색) 알고리즘 공유

관련 기사