Уровень сложности: Средняя (Medium)
Теги: Массив, Бинарный поиск, Вращённый массив
Условие задачи
Дан массив целых чисел nums, отсортированный в неубывающем порядке, но повёрнутый в неизвестной точке.
Массив может содержать дубликаты.
Проверьте, существует ли заданное целое число target в массиве.
Верните true, если target найден, иначе false.
💡 «Повёрнутый» означает: [0,1,2,4,4,4,5,6,6,7] может стать, например, [4,5,6,6,7,0,1,2,4,4].
Пример 1:
Ввод: nums = [2,5,6,0,0,1,2], target = 0
Вывод: true
Пример 2:
Ввод: nums = [2,5,6,0,0,1,2], target = 3
Вывод: false
Пример 3:
Ввод: nums = [1,0,1,1,1], target = 0
Вывод: true
Анализ задачи
Эта задача — расширение LeetCode 33 (Search in Rotated Sorted Array), но с важным отличием: в массиве могут быть дубликаты.
В LeetCode 33 мы легко определяли, какая половина отсортирована, сравнивая nums[mid] с nums[left] или nums[right].
Но при наличии дубликатов возможна ситуация:
nums[left] == nums[mid] == nums[right]
Например: [1,0,1,1,1] или [1,1,1,0,1]
В этом случае невозможно определить, в какой половине находится разрыв (pivot) — и стандартный бинарный поиск ломается.
💡 Ключевая идея:
- Если nums[left] == nums[mid] == nums[right], уменьшаем неопределённость, сдвигая left и right внутрь.
- В остальных случаях — работаем как в задаче без дубликатов: Определяем, какая половина гарантированно отсортирована
Проверяем, попадает ли target в эту отсортированную половину
Сужаем поиск
Это адаптированный бинарный поиск с обработкой неоднозначных случаев.
Решение на Java
Комментарии к коду:
- nums[left] == nums[mid] == nums[right] — «плохой» случай. Мы не можем решить, где отсортированная половина, поэтому сдвигаем обе границы.
- nums[left] <= nums[mid] — левая половина отсортирована (включая случай, когда left == mid).Проверяем, лежит ли target в диапазоне [nums[left], nums[mid]).
- Иначе — правая половина отсортирована, и мы проверяем диапазон (nums[mid], nums[right]].
- Обратите внимание на неравенства: < vs <= — важно для корректной обработки границ.
⚠️ В худшем случае (массив из одинаковых элементов, кроме одного), сложность деградирует до O(n), но в среднем — O(log n).
Объяснение «словами пятилетнего»
Представь, у тебя есть круглый циферблат, на котором числа идут по порядку:
0 → 1 → 2 → 3 → 4 → 5
Но кто-то повернул этот циферблат, и теперь он начинается с 3:
3 → 4 → 5 → 0 → 1 → 2
Ты хочешь найти, есть ли на нём число 1.
Если все числа разные, ты можешь быстро решить:
«Левая половина идёт по порядку? Тогда смотрю туда!»
Но что, если на циферблате много одинаковых чисел? Например:
1 → 1 → 1 → 0 → 1 → 1
Теперь, когда ты смотришь на середину, начало и конец — везде 1!
Ты не знаешь, где «порвался» порядок.
Тогда ты говоришь:
«Хорошо, я уберу по одной единице с краёв и посмотрю снова!»
И так, шаг за шагом, ты либо находишь нужное число, либо сужаешь круг, пока не поймёшь, что его нет.
Ты как детектив на круговой дорожке — ищешь, но умно! 😊
Заключение
Пример, рассмотренный в статье, можно найти по адресу:
https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task81_searchInRotatedSortedArraySecond/Solution.java