INTERPOLATION SEARCH

Dzintars Apeināns, Vasilijs Steklovs, Pēteris Grabusts

Abstract


Searching for information may take some time because of slow searching algorithm work. Some of searching algorithm work comparing needed value with all array's value of step by step. In this work will be looking about interpolation search which predict looking value place in array. Main idea is to compare searching algorithm by time which it take to find correct value and will make conclusions which of compared algrithm work faster with different size of array.

Keywords


Algorithm; interpolation; search

Full Text:

PDF

References


Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in o(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993 (angļu valodā, skatīts 2016.03.30)

Algoritmi: Interpolācijas meklēšana - http://www.stoimen.com/blog/2012/01/02/computer-algorithms-interpolation-search/ (angļu valodā, skatīts 2016.04.01)

Armenakis, A. C., Garey, L. E., Gupta, R. D., An adaptation of a root finding method to searching ordered disk files, BIT Numerical Mathematics, Volume 25, Number 4 / December, 1985. (angļu valodā, skatīts 2016.03.30)

Interpolācijas meklēšana datu struktūrā - https://www.quora.com/What-is-interpolation-search-in-data-structures (angļu valodā, skatīts 2016.04.02)

Interpolācijas meklēšanas algoritms - http://www.tutorialspoint.com/data_structures_algorithms/interpolation_search_algorithm.htm (angļu valodā, skatīts 2016.04.04)




DOI: http://dx.doi.org/10.17770/het2016.20.3500

Refbacks

  • There are currently no refbacks.