이진 검색 알고리즘

이진 검색은 이진 검색이라고도 하는데, 이는 보다 효율적인 검색 방법입니다. 그러나 이진 검색을 위해서는 선형 테이블이 순차적 저장 구조를 채택해야 하며 테이블의 요소는 키워드에 따라 순서대로 정렬되어야 합니다.

Find process

먼저, 테이블을 오름차순으로 정렬하고 테이블의 중간 위치에 기록된 키워드를 검색 키워드와 비교하여 두 개가 동일하면 검색에 성공한 것입니다. 그렇지 않으면 중간 위치 기록을 사용하여 테이블을 첫 번째와 검색 키워드로 나눕니다. 마지막 하위 테이블에서, 가운데에 기록된 키워드가 검색 키워드 키워드보다 크면 이전 하위 테이블을 추가로 검색하고, 그렇지 않으면 다음 하위 테이블을 추가 검색합니다. 조건에 맞는 레코드가 발견되어 검색이 성공할 때까지 또는 하위 테이블이 존재하지 않아 검색이 실패할 때까지 위 프로세스를 반복합니다.

비교 횟수

계산식:

시퀀스 테이블이 has n 키워드가 있는 경우:

검색에 실패하면 키워드를 최소 1회 비교하고, 검색에 성공하면 최대 키워드 비교 횟수는 b입니다.

참고: a, b, n은 모두 양의 정수입니다.

알고리즘 복잡성

이진 검색의 기본 아이디어는 n 요소를 대략 동일한 두 부분으로 나누고, a[n/ 2 ]를 x와 비교합니다. x=a[n/2]이면 x를 찾고 xa [n/2]이면 배열 a의 오른쪽 절반에서 x를 검색하면 됩니다.

시간 복잡도는 while 루프의 수에 지나지 않습니다!

총 n개의 요소가 있고,

은 점차적으로 n, n/2, n/4,...n/2^k를 따릅니다. 남은 숫자), 여기서 k는 사이클 수입니다.

n/2^k가 반올림되었으므로 >=1

즉, n/2^k=1입니다.

k=log2n임을 알 수 있습니다. (2를 밑으로 하는 n의 로그입니다.)

따라서 시간 복잡도는 O(h)=O로 표현할 수 있습니다. (log2n)# 🎜🎜#

다음은 이진 검색 구현을 위한 의사 코드를 제공합니다:

BinarySearch(max,min,des)

# 🎜🎜#mid -<(max+min)/2

while(min<=max)

mid=(min+max)/2

if mid=des then

return mid

elseif mid >des then

max=mid-1

else

min=mid+1

return max

반검색 방법은 이진 검색 방법이라고도 합니다. 요소 간의 순서를 최대한 활용 분할 정복 전략을 사용하는 관계는 최악의 경우 O(log n)에서 검색 작업을 완료할 수 있습니다. 기본 아이디어는 다음과 같습니다. (배열 요소가 오름차순으로 정렬되어 있다고 가정) n 요소를 대략 같은 수의 두 부분으로 나누고 a[n/2]를 가져와 x=인 경우 찾으려는 x와 비교합니다. a[n/ 2]이면 x가 발견되고 알고리즘이 종료됩니다. x

위 내용은 이진 검색 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!