Найти в Дзене
Записки о Java
2 подписчика

LeetCode №34: Find First and Last Position of Element in Sorted Array: Найти первое и последнее вхождение числа в отсортированном массиве

3
2 мин
Условие задачи:
Дан отсортированный по неубыванию массив целых чисел nums и целевое значение target.
Найдите начальный и конечный индексы target в массиве.
Если target не найден — верните [-1, -1].
Алгоритм должен работать за O(log n) времени — то есть требуется бинарный поиск. Примеры:nums = [5,7,7,8,8,10], target = 8 → [3, 4]
nums = [5,7,7,8,8,10], target = 6 → [-1, -1]
nums = [], target = 0 → [-1, -1]
Представь, что у тебя есть длинная полка с игрушками, выстроенными по цвету и размеру: 🟥 🟥 🟦 🟦 🟦 🟩 🟩 🟩 🟩 🟪 Ты ищешь все зелёные игрушки.
Но тебе нельзя перебирать всё подряд — это займёт слишком много времени! Вместо этого ты умный: И вот — ты знаешь, где начинаются и где заканчиваются зелёные игрушки!
И ты сделал это очень быстро, даже если полка огромная Потому что в условии сказано: O(log n).
Если делать линейный поиск (for по всему массиву), это будет O(n) — и на больших данных LeetCode выдаст Time Limit Exceeded. Но массив отсортирован! Это наш ключ.
Мы можем использов
Оглавление
Рисунок: задача с leetcode Find First And Last Position of Element in Sorted Array
Рисунок: задача с leetcode Find First And Last Position of Element in Sorted Array

Введение

Условие задачи:
Дан отсортированный по неубыванию массив целых чисел nums и целевое значение target.
Найдите начальный и конечный индексы target в массиве.
Если target не найден — верните [-1, -1].
Алгоритм должен работать за O(log n) времени — то есть требуется бинарный поиск.
Примеры:nums = [5,7,7,8,8,10], target = 8 → [3, 4]
nums = [5,7,7,8,8,10], target = 6 → [-1, -1]
nums = [], target = 0 → [-1, -1]

Объяснение для пятилетнего

Представь, что у тебя есть длинная полка с игрушками, выстроенными по цвету и размеру:

🟥 🟥 🟦 🟦 🟦 🟩 🟩 🟩 🟩 🟪

Ты ищешь все зелёные игрушки.
Но тебе нельзя перебирать всё подряд — это займёт слишком много времени!

Вместо этого ты умный:

  1. Сначала находишь первую зелёную — спрашиваешь: «А есть ли зелёная здесь или левее?»
  2. Потом находишь последнюю зелёную — спрашиваешь: «А есть ли зелёная здесь или правее?»

И вот — ты знаешь, где начинаются и где заканчиваются зелёные игрушки!
И ты сделал это очень быстро, даже если полка огромная

Почему нельзя просто пройти по массиву?

Потому что в условии сказано: O(log n).
Если делать линейный поиск (for по всему массиву), это будет O(n) — и на больших данных LeetCode выдаст Time Limit Exceeded.

Но массив отсортирован! Это наш ключ.
Мы можем использовать бинарный поиск дважды:

  • Один раз — чтобы найти первое вхождение.
  • Второй раз — чтобы найти последнее вхождение.

Как искать первое вхождение?

Обычный бинарный поиск останавливается, как только находит target.
Но нам нужно самое левое вхождение.

Идея:
Если nums[mid] == target, мы не останавливаемся, а продолжаем искать влево (right = mid - 1), потому что может быть ещё target левее.

Когда цикл завершится, left будет указывать на первое вхождение (если оно существует).

Как искать последнее вхождение?

Аналогично, но теперь, когда nums[mid] == target, мы идём вправо (left = mid + 1), чтобы найти самое правое вхождение.

После завершения цикла right будет указывать на последнее вхождение.

Решение на Java (с комментариями)

Рисунок: решение задачи, часть 1
Рисунок: решение задачи, часть 1
Рисунок: решение задачи, часть 2
Рисунок: решение задачи, часть 2
Рисунок: решение задачи, часть 3
Рисунок: решение задачи, часть 3

Пример работы

Массив: [5,7,7,8,8,10], target = 8

  • findFirst:Находит 8 в mid=4, но идёт влево → находит mid=3 → продолжает → right=2, цикл завершается.
    Возвращает 3.
  • findLast:Находит 8 в mid=3, идёт вправо → находит mid=4 → идёт дальше → left=5, цикл завершается.
    Возвращает 4.

→ Результат: [3, 4]

Заключение

Пример, рассмотренный в статье, можно найти по адресу:

https://github.com/ShkrylAndrei/leetcode/blob/main/src/main/java/info/shkryl/task34findFirstAndLastPositionOfElementInSortedArray/Solution.java