 It is also known that quantum algorithms can solve this problem faster, in formula_1 queries.The optimal algorithm is by Andris Ambainis.Yaoyun Shi first proved a tight lower bound when the size of the range is sufficiently large.