Найти слово в словаре неизвестного размера, используя только метод получения слова по индексу

Несколько дней назад у меня было собеседование в какой-то большой компании, имя не требуется :), и интервьюер попросил меня найти решение следующей задачи:

Предопределено: Есть словарь слов с неуказанным размером , мы просто знаем, что все слова в словаре отсортированы (например, по алфавиту). Также у нас есть только один метод

String getWord(int index) throws IndexOutOfBoundsException

Требуется: Необходимо разработать алгоритм поиска входного слова в словаре с использованием java. Для этого мы должны реализовать метод

public boolean isWordInTheDictionary(String word)

. Ограничения: Мы не можем изменить внутреннюю структуру словаря, у нас нет доступа к внутренней структуре, мы не знаем количество элементов в словаре.

Проблемы: Я разработал модифицированный бинарный поиск, и опубликует мой вариант (рабочий вариант) алгоритма, но есть ли другие варианты с логарифмической сложностью? У моего варианта сложность O (logN).

Мой вариант реализации:

public class Dictionary {
    private static final int BIGGEST_TOP_MASK = 0xF00000;
    private static final int LESS_TOP_MASK = 0x0F0000;
    private static final int FULL_MASK = 0xFFFFFF;
    private String[] data;
    private static final int STEP = 100; // for real test step should be Integer.MAX_VALUE
    private int shiftIndex = -1;
    private static final int LESS_MASK = 0x0000FF;
    private static final int BIG_MASK = 0x00FF00;


    public Dictionary() {
        data = getData();
    }

    String getWord(int index) throws IndexOutOfBoundsException {
        return data[index];
    }

    public String[] getData() {
        return new String[]{"a", "aaaa", "asss", "az", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "test", "u", "v", "w", "x", "y", "z"};
    }


    public boolean isWordInTheDictionary(String word) {
        boolean isFound = false;
        int constantIndex = STEP; // predefined step
        int flag = 0;
        int i = 0;
        while (true) {
            i++;
            if (flag == FULL_MASK) {
                System.out.println("Word is not found ... Steps " + i);
                break;
            }
            try {
                String data = getWord(constantIndex);
                if (null != data) {
                    int compareResult = word.compareTo(data);
                    if (compareResult > 0) {
                        if ((flag & LESS_MASK) == LESS_MASK) {
                            constantIndex = prepareIndex(false, constantIndex);
                            if (shiftIndex == 1)
                                flag |= BIGGEST_TOP_MASK;
                        } else {
                            constantIndex = constantIndex * 2;
                        }
                        flag |= BIG_MASK;

                    } else if (compareResult < 0) {
                        if ((flag & BIG_MASK) == BIG_MASK) {
                            constantIndex = prepareIndex(true, constantIndex);
                            if (shiftIndex == 1)
                                flag |= LESS_TOP_MASK;
                        } else {
                            constantIndex = constantIndex / 2;
                        }
                        flag |= LESS_MASK;
                    } else {
// YES!!! We found word.
                        isFound = true;
                        System.out.println("Steps " + i);
                        break;
                    }
                }
            } catch (IndexOutOfBoundsException e) {
                if (flag > 0) {
                    constantIndex = prepareIndex(true, constantIndex);
                    flag |= LESS_MASK;
                } else constantIndex = constantIndex / 2;
            }
        }
        return isFound;
    }

    private int prepareIndex(boolean isBiggest, int constantIndex) {
        shiftIndex = (int) Math.ceil(getIndex(shiftIndex == -1 ? constantIndex : shiftIndex));
        if (isBiggest)
            constantIndex = constantIndex - shiftIndex;
        else
            constantIndex = constantIndex + shiftIndex;
        return constantIndex;
    }

    private double getIndex(double constantIndex) {
        if (constantIndex <= 1)
            return 1;
        return constantIndex / 2;
    }
}