Поиск в отсортированном и повернутом массиве

Готовясь к собеседованию, я наткнулся на этот интересный вопрос:

Вам предоставили массив, который является отсортировано, а затем повернуто.

Например:

• Пусть arr = [1,2,3,4,5] , который отсортирован
• Дважды поверните вправо, чтобы получить [4,5,1 , 2,3] .

Теперь, как лучше всего искать в этом отсортированном + повернутом массиве?

Можно развернуть массив, а затем выполнить двоичный поиск. Но это не лучше, чем выполнять линейный поиск во входном массиве, поскольку оба являются наихудшим значением O (N).

Пожалуйста, укажите несколько указателей. Я много искал в Google специальные алгоритмы для этого, но не нашел ни одного.

Я понимаю C и C ++.