PHP 바이너리 검색에 대한 자세한 설명

이진 검색은 절반 검색이라고도 하며 비교 횟수가 적고 검색 속도가 빠르며 평균 성능이 좋다는 장점이 있습니다. 단점은 조회할 테이블이 순서가 지정된 테이블이어야 하며 삽입삭제라는 것입니다. 어렵다. 따라서 이진 검색 방법은 자주 변경되지 않지만 자주 검색되는 정렬된 목록에 적합합니다. 먼저, 테이블의 요소가 오름차순으로 배열되어 있다고 가정하고, 테이블의 중간 위치에 기록된 키워드와 검색 키워드를 비교하여 둘이 같으면 검색에 성공하고, 그렇지 않으면 중간 위치 기록을 사용합니다. 테이블을 첫 번째와 마지막 두 개의 하위 테이블로 나눕니다. 가운데에 기록된 키워드가 검색 키워드보다 크면 이전 하위 테이블을 더 검색하고, 그렇지 않으면 다음 하위 테이블을 검색합니다. 더 나아가. 조건에 맞는 레코드가 발견되어 검색이 성공할 때까지 또는 하위 테이블이 존재하지 않아 검색이 실패할 때까지 위 프로세스를 반복합니다.

이진 검색 방법을 사용하려면 배열이 순서 배열이어야 합니다

우리 배열이 증가하는 배열이라고 가정하면 먼저 배열의 중간 위치를 찾아야 합니다.

하나. 중간 위치를 알려면 시작 위치와 끝 위치를 알아야 하며 그런 다음 중간 위치의 값을 가져와 우리 값과 비교해야 합니다.

둘. 중간 값이 주어진 값보다 크다면, 이는 우리의 값이 중간 위치 이전이라는 뜻입니다. 이때, 중간 이전이기 때문에 변경해야 할 값은 입니다. 이때 끝 위치의 값은 이 시점에서 중간에 있습니다.

셋. 반면, 중간값이 우리가 제공하는 값보다 작다면, 주어진 값이 중간 위치 이후에 있다는 뜻이다. 이때, 뒷부분의 값은 2개로 다시 나눠져야 한다. 중간 값 뒤에 있으므로 변경해야 할 값은 시작 위치 값입니다. 이때 시작 위치의 값은 지정된 값을 찾을 때까지 현재 중간 위치여야 합니다.

넷. 아니면 중간값이 초기 시작 위치나 끝 위치(이 경우 주어진 값을 찾을 수 없음)와 같으면 코드를 이용하여 구현해 볼까요~

//循环实现
function getValue($num,$arr)
{
//查找数组的中间位置
$length=count($arr);
$start=0;
$end=$length;
$middle=floor(($start+$end)/2);
//循环判断
while($start>$end-1)
{
if($arr[middle]==$num)
{
return middle+1;
}elseif($arr[middle]<$num)
{
//如果当前要查找的值比当前数组的中间值还要打，那么意味着该值在数组的后半段
//所以起始位置变成当前的middle的值，end位置不变。
$start=$middle;
$middle=floor(($start+$end)/2);
}else{
//反之
$end=$middle;
$middle=floor(($start+$end)/2);
}}
return false;
}
 
//递归实现
/*
     * 从数组中获取元素值
     * @param1 int $num，要查找的目标值
     * @param2 array $arr，要查找的数组
     * @param3 int $start，查找的起始位置
     * @param4 int $end，查找的结束位置
     * @return mixed，找到了返回位置，没找到返回false
     */
     function getValue4($num,$arr,$start = 0,$end = 100){
        //采用二分法查找
        $middle = floor(($end + $start) / 2);

        //判断
        if($arr[$middle] == $num){
            //已经找到了，递归的出口
            return $middle + 1;
        }elseif($arr[$middle] < $num){
            //要查找的元素在数组的后半段
            $start = $middle + 1;
            //边界值
            if($start >= $end){
                //没有找到，但是已经超出边界值，递归出口
                return false;
            }
            //调用自己去查找：递归点
            return getValue4($num,$arr,$start,$end);    //getValue4($num,$arr,51,100)
        }else{
            //要查找的元素在数组的前半段
            $end = $middle - 1;
            //判断边界值
            if($end < 0)return false;

            //调用自己：递归点
            return getValue4($num,$arr,$start,$end);    //getValue4($num,$arr,0,49)
        }

        //都没有找到
        return false;
     }

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