New answers tagged


In his Algorithms Jeff Erickson discusses and analyses a similar variant, which he calls binary search (a terrible name, if you ask me): For a table of size a power of 2 when searching for key $k$, the idea is to check positions $h(k) \oplus r$, where $\oplus$ is bit-by-bit exclusive or and $r$ is the number of the try. It shares the benefit of quadratic ...

Top 50 recent answers are included