Как найти первую и последнюю позицию элемента в отсортированном массиве

Как найти первую и последнюю позицию элемента в отсортированном массиве

Комментарии
Содержание
  1. Проблема
    1. Наивный подход и его ограничения
  2. Решение
    1. Временная сложность

Проблема

В этой статье я расскажу о проблеме [Найти первую и последнюю позицию элемента в отсортированном массиве] (https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/).

Leetcode описывает проблему следующим образом:

Учитывая массив целых чисел nums, отсортированных в неубывающем порядке, найдите начальную и конечную позицию заданного значения target.

Если target не найдено в массиве, верните [-1, -1].

Вы должны написать алгоритм со сложностью времени выполнения O(log n).

Пример:

Вход: nums = [5,7,7,8,8,10], цель = 8

Выход: [3,4]

Leetcode оценивает эту задачу как среднюю. Я думаю, что это подходящая оценка. Решение выполнимо, но требует некоторого понимания алгоритма.

Наивный подход и его ограничения

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

Хотя этот подход работает, он требует O(n) времени для решения, что не удовлетворяет ограничению на O(log n) сложность во время выполнения. Поэтому он становится неэффективным при работе с большими наборами данных.

Решение

Чтобы достичь сложности выполнения O(log n), мы можем использовать бинарный поиск. Бинарный поиск возможен потому, что массив уже отсортирован. В этом оптимизированном подходе мы выполним два бинарных поиска:

  1. Поиск крайней левой позиции : Первый бинарный поиск найдет крайнее левое или первое вхождение целевого значения.
  2. Поиск крайнего правого положения : Второй двоичный поиск найдет крайнее правое или последнее вхождение целевого значения.

Вот как будет работать каждый двоичный поиск:

  1. Самая левая позиция : Инициализируем left в 0 и right в n - 1 (где n - длина массива). В цикле while вычислите средний индекс как (left + right) // 2. Если target > nums[mid], установите left = mid + 1. В противном случае установите right = mid - 1. После цикла проверьте, является ли nums[left] целью для подтверждения.
  2. Крайняя правая позиция : Инициализируйте left в 0 и right в n - 1 снова. На этот раз, если target >= nums[mid], установите left = mid + 1. В противном случае установите right = mid - 1. После цикла проверьте, является ли nums[right] целью для подтверждения.
  3. Наконец, верните [-1, -1], если местоположение левой и правой позиции пересекаются.

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

class Solution(object):
    def searchRange(self, nums, target):
        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if target > nums[mid]:
                left = mid + 1
            else:
                right = mid - 1
        левый_к_возврату = левый

        left, right = 0, len(nums) - 1
        while left <= right:
            mid = (left + right) / 2
            if target >= nums[mid]:
                left = mid + 1
            else:
                right = mid - 1

        если left_to_return <= right:
            return (left_to_return, right)
        else:
            return [-1, -1]

Вход в полноэкранный режим

Временная сложность

Каждый двоичный поиск имеет временную сложность O(log n), и поскольку мы выполняем два двоичных поиска, общая временная сложность остается O(log n).

Этот оптимизированный подход не только удовлетворяет алгоритмическому ограничению задачи, но и эффективно находит начальную и конечную позиции цели в массиве.