재귀적 및 비재귀적 구현을 ​​위한 PHP 이진 검색 예제 코드

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

이진 검색의 기본 아이디어는 n 요소를 대략 동일한 두 부분으로 나누고, x=a[n/2]인 경우 a[n/2]를 x와 비교하고, 다음과 같은 경우 알고리즘이 종료되는 것입니다. xarraya의 왼쪽 절반에서 searchx를 계속 검색하세요. x>a[n/2]인 경우 배열의 오른쪽 절반에서 아래 x.

를 검색하세요. a 예시 코드입니다

// 递归二分查找
$arr = [1,2,3,4,11,12,124,1245];
function bin_recur_find($arr, $beg, $end, $v) {
	if ($beg <= $end) {
		$idx = floor(($beg + $end)/2);
		if ($v == $arr[$idx]) {
			return $idx;
		} else {
			if ($v < $arr[$idx]) {
				return bin_recur_find($arr, $beg, $idx - 1, $v);
			} else {
				return bin_recur_find($arr, $idx + 1, $end, $v);
			}
		}
	}
	return -1;
}
// 非递归二分查找
function bin_find($arr, $v) {
	$beg = 0;
	$end = count($arr) - 1;
	while ($beg <= $end) {
		$idx = floor(($beg + $end)/2);
		if ($v == $arr[$idx]) {
			return $idx;
		} else {
			if ($v < $arr[$idx]) {
				$end = $idx - 1;
			} else {
				$beg = $idx + 1;
			}
		}
	}
	return -1;
}

echo bin_recur_find($arr, 0, count($arr) - 1, 100) . "\n";
echo bin_find($arr, 100) . "\n";

위 내용은 재귀적 및 비재귀적 구현을 ​​위한 PHP 이진 검색 예제 코드의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!