데이터 구조-보간 검색
보간 검색은 이진 검색의 개선 된 변형입니다. 이 검색 알고리즘은 필요한 값의 프로빙 위치에서 작동합니다. 이 알고리즘이 제대로 작동하려면 데이터 수집이 정렬 된 형식으로 균등하게 분산되어야합니다.
이진 검색은 선형 검색에 비해 시간 복잡성의 큰 이점이 있습니다. 선형 검색은 최악의 경우 복잡성이 Ο (n) 인 반면 이진 검색은 Ο (log n)입니다.
대상 데이터의 위치를 미리 알 수있는 경우가 있습니다. 예를 들어 전화 번호부의 경우 Morphius의 전화 번호를 검색하려면. 여기서는 'M'에서 시작하는 이름이 저장된 메모리 공간으로 바로 이동할 수 있으므로 선형 검색과 이진 검색조차 느려 보입니다.
이진 검색에서 위치 지정
이진 검색에서 원하는 데이터가 없으면 나머지 목록은 아래 부분과 높은 부분으로 나뉩니다. 검색은 둘 중 하나에서 수행됩니다.
데이터가 정렬 된 경우에도 이진 검색은 원하는 데이터의 위치를 검색하는 데 활용되지 않습니다.
보간 검색에서 위치 프로빙
보간 검색은 프로브 위치를 계산하여 특정 항목을 찾습니다. 처음에 프로브 위치는 컬렉션에서 가장 중간에있는 항목의 위치입니다.
일치가 발생하면 항목의 색인이 반환됩니다. 목록을 두 부분으로 나누기 위해 다음 방법을 사용합니다.
mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
where −
A = list
Lo = Lowest index of the list
Hi = Highest index of the list
A[n] = Value stored at index n in the list중간 항목이 항목보다 크면 프로브 위치가 중간 항목 오른쪽에있는 하위 배열에서 다시 계산됩니다. 그렇지 않으면 항목은 중간 항목의 왼쪽에있는 하위 배열에서 검색됩니다. 이 프로세스는 하위 배열의 크기가 0으로 줄어들 때까지 하위 배열에서도 계속됩니다.
보간 검색 알고리즘의 런타임 복잡성은 Ο(log (log n)) 비교하자면 Ο(log n) 유리한 상황에서 BST의.
연산
기존 BST 알고리즘을 즉석에서 구현 한 것이므로 위치 프로빙을 사용하여 '대상'데이터 값 인덱스를 검색하는 단계를 언급하고 있습니다.
Step 1 − Start searching data from middle of the list.
Step 2 − If it is a match, return the index of the item, and exit.
Step 3 − If it is not a match, probe position.
Step 4 − Divide the list using probing formula and find the new midle.
Step 5 − If data is greater than middle, search in higher sub-list.
Step 6 − If data is smaller than middle, search in lower sub-list.
Step 7 − Repeat until match.의사 코드
A → Array list
N → Size of A
X → Target Value
Procedure Interpolation_Search()
Set Lo → 0
Set Mid → -1
Set Hi → N-1
While X does not match
if Lo equals to Hi OR A[Lo] equals to A[Hi]
EXIT: Failure, Target not found
end if
Set Mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])
if A[Mid] = X
EXIT: Success, Target found at Mid
else
if A[Mid] < X
Set Lo to Mid+1
else if A[Mid] > X
Set Hi to Mid-1
end if
end if
End While
End ProcedureC 프로그래밍 언어의 보간 검색 구현에 대해 알아 보려면 여기를 클릭하십시오 .