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

怪我咯
풀어 주다: 2023-03-13 22:52:02
원래의
2139명이 탐색했습니다.

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

이진 검색의 기본 아이디어는 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

관련 라벨:
원천:php.cn
본 웹사이트의 성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
인기 튜토리얼
더>
최신 다운로드
더>
웹 효과
웹사이트 소스 코드
웹사이트 자료
프론트엔드 템플릿
회사 소개 부인 성명 Sitemap
PHP 중국어 웹사이트:공공복지 온라인 PHP 교육,PHP 학습자의 빠른 성장을 도와주세요!