PHP 구현 이분 검색 알고리즘

이분 검색

이분 검색은 반쪽 검색(Binary Search)이라고도 하는데, 효율적인 검색 방법입니다.단, 반쪽 탐색을 위해서는 선형 테이블이 순차적으로 저장되어야 하며, 테이블 안의 요소가 키워드에 따라 정렬되어야 한다.

먼저, 표 안의 요소가 오름차순으로 배열되어 있다고 가정하고, 표의 중간 위치 기록의 키워드와 검색 키워드를 비교하며, 만약 양자가 같다면 검색이 성공한다. 그렇지 않으면 중간 위치 기록을 이용하여 표를 앞, 뒷 두 개의 하위 표로 나눈다.중간 위치에 기록된 키워드가 검색 키보다 크면 이전 하위 테이블을, 그렇지 않으면 이전 하위 테이블을 찾습니다.조건을 만족시키는 레코드를 찾을 때까지 반복하거나, 하위 테이블이 존재하지 않을 때까지 검색을 수행할 수 없습니다.



순환 방법을 사용하여 이분 검색하기

/**
 * 바이너리서치(Binary Search) 알고리즘은 반쪽 찾기 알고리즘이라고도 한다.이분법적으로 찾는 사상은 매우 간단하며, 약간 분치된 사상과 유사하다。
 * 이분 탐색은 질서 있는 데이터 집합을 겨냥하여 매번 구간의 중간 원소와 대비를 통과한다，
 * 찾을 요소를 찾을 때까지 찾을 구간을 이전 절반으로 축소하거나 0으로 축소합니다。
 *
 * 라운드 로빈 방식
 * @param array $array      찾을 배열
 * @param int $findVal      찾을 값
 * @return int              검색된 배열 키를 되돌려줍니다
 */
function binarySearch($array, $findVal)
{
    // 배열이 아니거나 배열이 비어 있으면 -1로 돌아갑니다
    if (!is_array($array) || empty($array)) {
        return -1;
    }
    // 구간 찾기，시작점과 끝점
    $start = 0;
    $end = count($array) - 1;
    while ($start <= $end) {
        // 중간점을 참조점으로 하여 정수를 취하다
        $middle = intval(($start + $end) / 2);
 
        if ($array[$middle] > $findVal) {
            //찾을 수가 기준점보다 작으면 찾을 수가 왼쪽에 있습니다
            // $middle이 이미 비교되었기 때문에 여기서는 1을 빼야 한다
            $end = $middle - 1;
 
        } elseif ($array[$middle] < $findVal) {
            // 찾을 수가 기준점보다 크면 찾을 수가 오른쪽에 있습니다
            // $middle이 이미 비교되었기 때문에 여기에 1을 더해야 합니다
            $start = $middle + 1;
 
        } else {
            //조회 수가 기준점과 같으면, 찾아 되돌려줍니다
            return $middle;
        }
    }
    // 찾을 수 없음, 반환 - 
    return -1;
}
 
//호출하다
$array = [10,12,16,19,20,34,56,78,84,95,100];
echo binarySearch($array, 84);

재귀적 방법을 사용하여 이분법적 검색을 실현하다

/**
 * 재귀적 표기법
 * @param array $array  찾을 배열
 * @param int $findVal  찾을 값
 * @param int $start    찾기 구간, 시작점
 * @param int $end      구간 찾기, 종점 찾기
 * @return int          검색된 배열 키를 되돌려줍니다
 */
function binarySearch($array, $findVal, $start, $end)
{
    // 중간점을 참조점으로 하여 정수를 취하다
    $middle = intval(($start + $end) / 2);
    if ($start > $end) {
        return -1;
    }
    if ($findVal > $array[$middle]) {
        // 찾을 수가 기준점보다 크면 찾을 수가 오른쪽에 있습니다
        return binarySearch($array, $findVal, $middle + 1, $end);
 
    } elseif ($findVal < $array[$middle]) {
        // 찾을 수가 기준점보다 작으면 찾을 수가 왼쪽에 있습니다
        return binarySearch($array, $findVal, $start, $middle - 1);
 
    } else {
        return $middle;
    }
}
 
// 호출하다
$array = [10,12,16,19,20,34,56,78,84,95,100];
echo binarySearch($array, 95, 0, count($array)-1);