지수 검색

컴퓨터 과학에서 기하급수적 검색(두 배로 검색하거나 질주하는 검색 또는 스트루지크 검색이라고도 함)^[1]은 1976년 존 벤틀리와 앤드류 치치 야오가 정렬되고 무한 목록을 검색하기 위해 만든 알고리즘이다.^[2]검색 키가 상주하는 범위를 결정하고 해당 범위 내에서 이진 검색을 수행하는 가장 일반적인 존재와 함께 이를 구현하는 수많은 방법이 있다.검색 키가 목록에 있는 경우 목록에서 검색 키의 위치인 O(log i) 또는 검색 키가 목록에 없는 경우 검색 키가 있어야 하는 위치인 경우 O(log i)가 필요하다.

지수 검색은 경계 목록에서 검색하는 데도 사용할 수 있다.지수 검색은 검색되는 요소가 배열의 시작에 가까울 때 바이너리 검색과 같은 경계 목록에 대한 전통적인 검색보다 더 많은 검색을 수행할 수 있다.지수 검색은 O(log i) 시간에 실행되는 반면, 이진 검색은 O(log n) 시간에 실행되며, 여기서 n은 목록의 요소 수입니다.

알고리즘.

지수 검색은 지정된 입력 값("키" 검색)에 대해 정렬되고 바인딩되지 않은 목록을 검색할 수 있다.알고리즘은 두 단계로 구성된다.첫 번째 단계는 검색 키가 목록에 있을 경우 위치할 범위를 결정한다.두 번째 단계에서는 이 범위에 대해 이진 검색이 수행된다.첫 번째 단계에서 리스트가 오름차순으로 정렬된다고 가정하면 알고리즘은 첫 번째 지수인 j를 찾는데 여기서^j 값 2가 검색 키보다 크다.이 값, 2는^j 이전 검정력 2, 2로^{j - 1} 이진 검색의 상한 값이 되며 이진 검색의 하한이 된다.^[3]

// 길이 크기의 배열 arr에서 키의 위치를 반환한다. 템플릿 <타이프 이름 T> 인트로 지수_검색(T arr[], 인트로 사이즈를 맞추다, T 핵심을) {     만일 (사이즈를 맞추다 == 0) {         돌아오다 NOT_Found;     }      인트로 묶인 = 1;     하는 동안에 (묶인 < 사이즈를 맞추다 && arr[묶인] < 핵심을) {         묶인 *= 2;     }      돌아오다 binary_search(arr, 핵심을, 묶인/2, 분(묶인 + 1, 사이즈를 맞추다)); } 

각 단계에서 알고리즘은 검색 키 값과 현재 검색 인덱스의 키 값을 비교한다.현재 인덱스의 요소가 검색 키보다 작을 경우 알고리즘이 반복되며 다음 검색 인덱스를 두 배로 늘려 다음 검색 인덱스로 건너뛰어 다음 검정력 2를 계산한다.^[3]현재 인덱스의 요소가 검색 키보다 크면 알고리즘은 이제 검색 키가 목록에 아예 포함되어 있으면 이전 검색 인덱스 2와^{j - 1} 현재 검색 인덱스 2로^j 형성된 간격에 위치한다는 것을 알고 있다.그런 다음 검색 키가 목록에 없는 경우, 또는 목록에서 검색 키의 위치를 사용하여 이진 검색을 수행한다.

퍼포먼스

알고리즘의 첫 번째 단계는 O(log i) 시간이 걸리는데, 여기서 i는 검색 키가 목록에 있는 색인이다.이는 바이너리 검색의 상한을 결정할 때, 반면 루프는 정확히 $\lceil {\displaystyle }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ (${\displaystyle i}$) ${\displaystyle \rceil }$ ${\displaystyle \lceil \log(i)\rceil$}번$$ 실행되기 때문이다.Since the list is sorted, after doubling the search index ${\displaystyle \lceil \log(i)\rceil }$ times, the algorithm will be at a search index that is greater than or equal to i as ${\displaystyle 2^{\lceil \log(i)\rceil }\geq i}$. As such, the first stage of the algorithm takes O(log i) time.

알고리즘의 두 번째 부분 역시 O(log i) 시간이 걸린다.2단계는 단순한 이진 검색이기 때문에, n은 검색되는 간격의 크기인 O(log n)가 필요하다.이 간격의 크기는 위에서 본 바와^{j - 1} 같이 j = log i인 경우^j 2 - 2가 될 것이다.이는 검색되는 간격의 크기가 2^{log i} - 2 = 2라는^{log i - 1log i - 1} 것을 의미한다.이렇게^{log i - 1} 하면 로그 (2) = 로그 (i) - 1 = O(log i)의 실행 시간이 주어진다.

이것은 알고리즘에 O(log i) + O(log i) = 2 O(log i) = O(log i)의 두 단계의 런타임을 합산하여 계산한 총 런타임을 제공한다.

대안

벤틀리와 야오는 지수 탐색을 위해 몇 가지 변형을 제안했다.^[2]이러한 변화는 알고리즘의 두 번째 단계에서 바이너리 검색에 대한 상한을 결정할 때 단항 검색과 달리 바이너리 검색을 수행하는 것으로 구성된다.이것은 알고리즘의 첫 번째 단계를 두 부분으로 나누어서 알고리즘을 전체적으로 3단계 알고리즘으로 만든다.새로운 1단계에서는 ${\displaystyle {2j{}^{}}^{}}$ ${\displaystyle {{\prime }^{}}^{}}$ ${\$ 2$^{j'}}$이 검색키보다 $크고{\displaystyle {\mathrm{}}^{}}$ ${\displaystyle {2j{}^{}//2\mathrm{}}^{}}${\$displaystyle$ 2$^{j'/2$}}이$$ 검색키보다 낮아지는 등 이전과 매우 유사한$$값 $j{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을 결정한다.이전에는 $j{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$이(가) 2의 다음 힘(즉, j에 1을 더하는 것)을 계산하여 일률적으로 결정되었다$$.변동에서는 $j{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$을(를) 대신 두 배로 하는$$ 것이 제안된다(예: 2와³ 반대로 2에서² 2로⁴ 점프).${\displaystyle {2j{}^{}}^{}}$ ${\displaystyle {{\prime }^{}}^{}}$ ${\$보다 검색 키가 커지면$$ 이전보다 훨씬 거친 상한이 형성된다.이 $j{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$이(가) 발견되면 알고리즘이 두 ${\displaystyle 번째\mathrm{}}$ 단계로 이동하고 $j{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$/ 2 ${\displaystyle$ j$'/2}$ 및 $j$ ${\displaystyle {\prime }^{}}$ ${\$에 의해 형성된 간격에 대해 이진 검색이 수행되어 보다 정확한 상한 지수 j를 제공한다$.$여기서 알고리즘의 세 번째 단계는 이전과 같이 구간 2와^{j - 1} 구간^j 2에서 바이너리 검색을 수행한다.이 변동의 성능은 ${\displaystyle \lfloor }$ ${\displaystyle \mathrm{로그}}$ log ${\displaystyle i}$⌋${\displaystyle }$+ ${\displaystyle 2}$ ${\displaystyle \lfloor }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle }$ ${\displaystyle (\lfloor i}$ ${\displaystyle i+}$ +${\displaystyle 1}$ )${\displaystyle +}$ + 1 ${\displaystyle \lfloor \log i\rfloor +2\llfloor \llog(\l$ 플로어 $\log i\rfloor$+1)$$= O(log i$)$이다.

Bentley와 Yao는 알고리즘의 첫 번째 단계에서 이진수 k가 수행되는 것으로 이 변동을 일반화하여 k-중첩된 이진수 검색 변동을 제공한다.점증적 런타임은 원래의 지수적 검색 알고리즘과 마찬가지로 O(log i) 시간으로 실행되는 변동에 대해 변경되지 않는다.

또한 정렬된 배열에서 k-중첩된 이진 검색의 위의 결과를 사용할 때 동적 핑거 속성의 엄격한 버전을 가진 데이터 구조를 제공할 수 있다.^[4]이를 이용하여 검색 시 수행되는 비교 횟수는 log (d) + log (d) + log (d) + … + O(log d)이며, 여기서 d는 마지막으로 접근한 원소와 접근한 현재 원소의 순위 차이다.

참고 항목

• 선형검색
• 이진 검색
• 보간검색
• 3차 검색
• 해시 테이블

참조