PHP는 이진 검색 알고리즘을 구현합니다(자세한 코드 설명).

이진 검색은 절반 검색이라고도 합니다. 이진 검색 알고리즘을 사용하려면 데이터가 순서대로 있어야 합니다. 다음은 PHP에서 이진 검색 알고리즘을 구현하는 코드입니다.

1: 재귀적 방법

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
$low = 0;
$high = count($array)-1;
function bin_search($array, $low, $high, $target){
    if ( $low <= $high){
        var_dump($low, $high);echo "\n";
        $mid =  intval(($low+$high)/2 );
        if ($array[$mid] ==  $target){
            return true;
        }elseif ( $target < $array[$mid]){
            return  bin_search($array, $low,  $mid-1, $target);
        }else{
            return  bin_search($array, $mid+ 1, $high, $target);
        }
    }
    return false;
}
$find = bin_search($array, $low, $high, $target);
var_dump($find);

실행 결과

int(0)
int(25)
int(13)
int(25)
int(20)
int(25)
int(20)
int(21)
bool(true)

우리는 4번의 이진 검색 후에 이를 볼 수 있습니다. 간격은 지속적으로 반으로 접혀지고 마침내 $target이 발견됩니다.

2: 루프 방식

$array = [1,3,6,9,13,18,19,29,38,47,51,56,58,59,60,63,65,69,70,71,73,75,76,77,79,89];
$target = 73;
function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$mid] == $target){
                $find = true;
                break;
            } elseif ($array[$mid] < $target){
                $low = $mid+1;
            } elseif ($array[$mid] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);
var_dump($find);

실행 결과

int(0)
int(25)
int(13)
int(25)
int(20)
int(25)
int(20)
int(21)
bool(true)

둘의 과정과 결과를 보면 방법은 동일합니다. 연관 배열에 대한 이진 검색 알고리즘을 테스트해 보겠습니다.

$array = ['a'=>1,'b'=>3,'c'=>6,'d'=>9,'e'=>13,'f'=>18,'g'=>19,'h'=>29,'i'=>38];
$target = 19;
function bin_search($array, $target)
{
    $low = 0;
    $high = count($array)-1;
    $key_map = array_keys($array);
    $find = false;
    while (true){
        if ($low <= $high){
            var_dump($low, $high);echo "\n";
            $mid = intval(($low + $high)/2);
            if ($array[$key_map[$mid]] == $target){
                $find = true;
                break;
            } elseif ($array[$key_map[$mid]] < $target){
                $low = $mid+1;
            } elseif ($array[$key_map[$mid]] > $target){
                $high = $mid-1;
            }
        } else {
            break;
        }
    }
    return $find;
}
$find = bin_search($array, $target);
var_dump($find);
执行结果
int(0)
int(8)
int(5)
int(8)
bool(true)

두 개의 이진 검색에서 $target이 발견되었습니다. 연관 배열의 경우 PHP의 array_keys 함수를 사용하여 연관 순서 키를 얻고 값을 간접적으로 비교합니다. 키를 통한 $target 및 $array의 ​​.

위 내용은 PHP는 이진 검색 알고리즘을 구현합니다(자세한 코드 설명).의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!