find-in-a-mountain-array.md

Find In a Mountain Array

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

• arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
• arr[i] > arr[i + 1] > ... > arr[arr.length - 1]

Данные доступны не напрямую, а через определенный интерфейс:

• MountainArray.get(k) — вернет элемент по индексу k;
• MountainArray.length() — вернет длину массива.

Нужно найти индекс заданного target .

Задача на LeetCode.

Вопросы

На собеседовании важно задавать уточняющие вопросы, чтобы полностью понять условия задачи.

1. Уточнение входных данных:

• Каково минимальное и максимальное значение элемента в массиве? Могут ли быть отрицательные числа?

  В отрезке [0, 10^9]

• Может ли быть несколько правильных ответов или только один?

  Действительно, target может встречаться несколько раз. Нужно вернуть наименьший индекс.

• Есть ли гарантия, что в массив непустой? Какая минимальная длина?

  Три элемента.

• Есть ли гарантия, что в массиве всегда будет ответ?

  Нет. Если элемента нет нужно вернуть -1 .

• Какова максимальная длина массива?

  ~ 10^4

• Все ли участки строго возврастают / убывают или возможны участки плато?

Строго возрастают или убывают. Плато запрещены.

• Возможны ли несколько локальных пиков или пик строго один?

Строго один.

2. Ограничения задачи:

• Насколько дорогая операция get? Подойдет ли линейное решение (~10^4 вызовов get)?

Операция get относительно дорогая. В идеале, надо сделать не более 100 вызовов get .

• Можем ли мы считать, что операции get стоят одинаково для любого индекса?

Да. Сложность вызова get — O(1) , то есть не зависит от индекса.

Примеры

1. Пример 1:

Входные данные: массив = [1, 2, 3, 4, 5, 3, 1], target = 3

Результат: 2

Число 3 присутствует в массиве и находится по индексам 2 и 5. Возвращается минимальный индекс, который равен 2.

1. Пример 2:

Входные данные: массив = [0, 1, 2, 4, 2, 1], target = 3

Результат: -1

3 нет в массиве, поэтому возвращаем -1.

Решение

При ограниченных на количество вызовов get нет варианта, кроме бинарного поиска.

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

Бывает полезно искусственно упростить задачу как бы рассматривая элемент задачи. Допустим наш массив — строго возрастает, то есть это часть до пика, а сам пик это последний элемент. Как это поможет?

В таком случае мы знаем что спрашивать у бинарного поиска. Поделили пополам и спросили «середина больше или меньше target »? Если больше — надо продолжить искать слева, в противном случае справа.

Хорошо, а если массив строго убывает, то есть это часть после пика. В таком случае так же можем применить бинарный поиск, только на этот раз если середина больше target — надо продолжить искать справа, в противном случае слева.

Нам известно, что пик строго один. Значит, надо если его найти, то мы поделим массив на две части, к каждой из которых можно применить бинарный поиск как описано выше.

Как найти пик? Еще один бинарный поиск 😊

Итак, алгоритм:

• найти пик бинарным поиском
• поискать target слева от пика, бинарным поиском
  • если target найден — возвращаем его индекс
  • если не найден:
    • поискать target справа от пика, бинарным поиском
      • если target найден — возвращаем его индекс
      • если не найден — возращаем -1

Сможем ли мы уложиться в ограничение на количество вызовов get ?

Три бинарных поиска, где нужно звать get не более log 10^4 плюс при нахождении пика нужно звать get дважды на каждом шаге (для двух соседних элементов), то есть не более 2 * log 10^4 . В итоге, 4 * log 10^4 (где lg это логарифм по основанию 2) < 56. Отлично!

Завершаем, как обычно, тестированием алгоритма на нескольких примерах по шагам.

P. S. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗

Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.