Могу поделиться светлой мыслью: массив строк нужно отсортировать, и искать в нём бинарным поиском, т.е. сначала сравниваем со строкой, которая посередине, потом, в зависимости от результата сокращаем интервал поиска вдвое (либо верхнюю часть берём, либо нижнюю). Время на сортировку, конечно, потребуется, но если количество поисков сравнимо с количеством строк в массиве, то бинарный поиск стопудово выиграет. Если же массив каждый раз разный, т.е. количество поисков всегда "один", то тут видимо уже ничего не поделаешь, по крайней мере, на вскидку, хорошего решения в голову не пришло.