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;

요약:

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

위 내용은 PHP 순서 테이블 검색 - 이진 검색(반감기) 내용입니다. 더 많은 관련 내용은 PHP 중국어 홈페이지(www.php.cn)를 참고해주세요!