При запросе "finger search" все ссылки вели на поиск внутри дерева, из-за этого я думал, что придется от сортированного массива переходить к другой структуре. А Википедию действительно невнимательно прочитал, там для случая отсортированного массива этот самый exponential search и приводится, оказывается.