Найти дубликат в отсортированном массиве за меньшее линейное время

Сегодня интервьюер задал мне этот вопрос. Я немедленно ответил, что мы можем просто выполнить линейный поиск, сравнивая текущий элемент с предыдущим элементом в массиве. Затем он спросил меня, как эту проблему можно решить за меньшее, чем линейное время.

Предположения

• Массив отсортирован
• Имеется только одиндубликат
• Массив толькозаполнен числами [0, n], где n— длина массива.

Пример массива: [0,1,2,3,4,5,6,7,8,8,9]

Я попытался придумать алгоритм «разделяй и властвуй» для решения это, но я не уверен, что это был правильный ответ. У кого-нибудь есть идеи?