From some homework I did as a freshman, I remember another neat data structure with O(sqrt(n)) search: <a href="https:&#x2F;&#x2F;ece.uwaterloo.ca&#x2F;~dwharder&#x2F;aads&#x2F;Algorithms&#x2F;Beaps&#x2F;" rel="nofollow">https:&#x2F;&#x2F;ece.uwaterloo.ca&#x2F;~dwharder&#x2F;aads&#x2F;Algorithms&#x2F;Beaps&#x2F;</a>