블록 보간 탐색법 = Block Interpolation Search

다국어 초록 (Multilingual Abstract)

The binary and interpolation search algorithms are the most famous among search area algorithms, the former running in $O(log_2n)$ on average, and the latter in $O(log_2log_2n)$ on average and O(n) at worst. Also, the interpolation search use only the probability of key value location without priori information. This paper proposes another search algorithm, which I term a 'hybrid block and interpolation search'. This algorithm employs the block search, a method by which MSB index of a data is determined as a block, and the interpolation search to find the exact location of the key. The proposed algorithm reduces the search range with priori information and search the reduced range with uninformed situation. Experimental results show that the algorithm has a time complexity of $O(log_2log_2n_i)$, $n_i{\simeq}0.1n$ both on average and at worst through utilization of previously acquired information on the block search. The proposed algorithm has proved to be approximately 10 times faster than the interpolation search on average.

참고문헌 (Reference)

1 이상운, "빠른 계수 정렬법의 제안" 한국인터넷방송통신학회 15 (15): 61-68, 2015

2 이상운, "범위 피벗 퀵정렬" 한국컴퓨터정보학회 17 (17): 139-145, 2012

3 이상운, "가상의 기수계수버킷 정렬" 한국인터넷방송통신학회 15 (15): 95-102, 2015

4 D. Knuth, "The Art of Computer Programming 3(3rd ed.), Section 6.1: Sequential Searching" Addison-Wesley 396-408, 1997

5 A. R. Chadha, "Modified Binary Search Algorithm" 7 (7): 37-40, 2014

6 T. H. Cormen, "Introduction to Algorithms" MIT Press 2005

7 David E. Ferguson, "Fibonaccian searching" Association for Computing Machinery (ACM) 3 (3): 648-, 1960

8 STEPHEN R. SHOROFSKY, "Comparison of Step-Down and Binary Search Algorithms for Determination of Defibrillation Threshold in Humans" Wiley-Blackwell 27 (27): 218-220, 2004

9 A. Arne, "Automata, Languages and Programming" 5-27, 1993

10 Gaston H. Gonnet, "An algorithmic and complexity analysis of interpolation search" Springer Nature 13 (13): 39-52, 1980

11 R. Sedgewick, "Algorithms in C, Parts 1-4:Fundamentals, Data Structures, Sorting, Searching" Addison-Wesley 1998

12 C. A. R. Hoare, "Algorithm 64: Quicksort" Association for Computing Machinery (ACM) 4 (4): 321-327, 1961

13 이상운, "3-점 평균 피벗 퀵정렬" 한국인터넷방송통신학회 14 (14): 295-301, 2014