Square binary search

This article or the following section is not adequately provided with supporting documents ( e.g. individual evidence ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

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. ${\displaystyle {\sqrt {n}}}$

In this way, given a list of length n, the search space is reduced to a list of length with each recursive step . ${\displaystyle {\sqrt {n}}}$

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 . ${\displaystyle {\mathcal {O}}(\log(\log(n)))}$ ${\displaystyle {\mathcal {O}}({\sqrt {n}})}$

Individual evidence

1. ↑ Search in linear fields (PDF; 142 kB), Graz University of Technology