Существование элемента в массиве

[B_N]

Можно завести бинарное дерево в соответствии с разложением числа по степеням двойки, "развесить" по нему числа из массива и на последней ветке повесить массив из всех индексов раскладывающегося таким образом числа в начальном массиве. Тогда всё сводится 1) к проходу по дереву (до 32-х уровней) 2) поиску в массиве индексов (вряд ли он будет большим) индексов таких, что l <= i <= r, если такое число вообще содержится в дереве 3) предварительному выходу из поиска, если число не нашлось. Можно, в принципе, оптимизировать дерево - разбивать число не побитно, а побайтно, скажем, тогда в каждом узле будет массив.