Сортированные массивы — это распространенная структура данных, используемая в программировании. Одной из распространенных задач при работе с отсортированными массивами является поиск первой и последней позиций определенного элемента. В этой статье блога мы рассмотрим различные методы выполнения этой задачи, используя разговорные объяснения и приведем примеры кода на JavaScript и Python.

Метод 1: линейный поиск
Самый простой способ найти первую и последнюю позиции элемента в отсортированном массиве — выполнить линейный поиск. Мы перебираем массив и отслеживаем первое и последнее появление целевого элемента. Вот пример реализации на JavaScript:

function findFirstAndLastLinear(arr, target) {
  let first = -1;
  let last = -1;

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) {
      if (first === -1) {
        first = i;
      }
      last = i;
    }
  }

  return [first, last];
}

Метод 2: двоичный поиск
Двоичный поиск — более эффективный подход при работе с отсортированными массивами. Мы воспользуемся модифицированным алгоритмом двоичного поиска, чтобы найти первое вхождение целевого элемента. Затем мы выполним еще один двоичный поиск, чтобы найти последнее вхождение. Вот пример реализации на Python:

def findFirstAndLastBinary(arr, target):
    def binarySearch(arr, target, findFirst):
        start = 0
        end = len(arr) - 1
        result = -1
        while start <= end:
            mid = start + (end - start) // 2
            if arr[mid] == target:
                result = mid
                if findFirst:
                    end = mid - 1
                else:
                    start = mid + 1
            elif arr[mid] < target:
                start = mid + 1
            else:
                end = mid - 1
        return result
    first = binarySearch(arr, target, True)
    last = binarySearch(arr, target, False)
    return [first, last]

Метод 3: методы массивов JavaScript
JavaScript предоставляет встроенные методы массивов, которые можно использовать для поиска первой и последней позиций элемента. Мы можем использовать indexOf, чтобы найти первое вхождение, и lastIndexOf, чтобы найти последнее вхождение. Вот пример реализации:

function findFirstAndLastArrayMethods(arr, target) {
  const first = arr.indexOf(target);
  const last = arr.lastIndexOf(target);

  return [first, last];
}

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