Найдите любое из нескольких возможных повторяющихся целых чисел в списке

Дан массив из n + 1 целых чисел, каждое в диапазоне от 1 до n , найдите повторяющееся целое число.

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

top = 0;
bot = 0;
for i=1:n+1
  if P[i] > n/2 
    top = top+1;
  else
    bot = bot+1;
end

Итак, я утверждаю, что один из них, top или бот , снова должен быть больше n / 2 на PhP. Возьмите этот диапазон и повторите.

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