Вопрос на собеседовании - поиск в отсортированном массиве X по индексу i, так что X [i] = i

Вчера в моем интервью мне задали следующий вопрос:

Рассмотрим массив Java или C ++, скажем X , который отсортирован, а не два элемента в нем одинаковы. Как лучше всего найти индекс, скажем, i , такой, что элемент с этим индексом также будет i . То есть X [i] = i .

В качестве пояснения она также привела мне пример:

Array X : -3 -1 0 3 5 7
index   :  0  1 2 3 4 5

Answer is 3 as X[3] = 3.

Лучшее, что я мог подумать, - это линейный поиск. После собеседования я много думал об этой проблеме, но не мог найти лучшего решения. Мой аргумент: элемент с требуемым свойством может находиться в любом месте массива. Так что он также может находиться в самом конце массива, поэтому нам нужно проверить каждый элемент.

Я просто хотел подтвердить от сообщества, что я прав. Пожалуйста, скажите мне, что я прав :)