Square binary search
Quadratic binary search is a search algorithm similar to binary search or interpolation search . It tries to avoid the disadvantages of the interpolation search by reducing the interval in each recursion step.
idea
According to the pattern of the interpolation search , the presumed position k is first interpolated in each recursive step . Then - in order to avoid the disadvantages of the interpolation search - the interval of the length in which the searched value is located is searched for. The next recursive search call is applied to this interval.
In this way, given a list of length n, the search space is reduced to a list of length with each recursive step .
complexity
As with the interpolation search, in the middle case there is a running time of , but in the worst case only a running time of .
Individual evidence
- ↑ Search in linear fields (PDF; 142 kB), Graz University of Technology