Добро пожаловать в раздел Разгадывание математических загадок с помощью JavaScript. JavaScript — один из самых популярных и высокооплачиваемых языков программирования в наши дни. Это также один из самых простых языков программирования для написания кода.

Мы решили опубликовать серию статей о задачах по математике и о том, как их решать с помощью JavaScript.

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

  1. Вы должны быть знакомы с JavaScript, OOJS и ES2015 и выше.
  2. Вы должны быть знакомы со структурами данных и алгоритмами.

Достаточно сказано! Давайте начнем…

Найти наименьший элемент в отсортированном повернутом массиве

Прежде чем мы начнем, давайте разберемся, что такое повернутый массив. Предположим, есть список чисел 1, 2, 3, 4 и 5. Если я поверну этот список на позицию 2 для данного массива, список станет [5, 1, 2, 3, 4]. Если я поверну список на позицию 4, он по существу станет [2, 3, 4, 5, 1]. Как найти наименьший элемент
(или n-й наименьший элемент) в таком массиве?

Ответ прост: найдите элемент, чей предыдущий родственный элемент больше по значению. Но прежде чем мы перейдем к решению, давайте рассмотрим простое решение JavaScript с использованием методов встроенной библиотеки.

Решение 1. Прямолинейный подход

function findSmallest(arr = []) {
  const smallest = arr.find((el, index) => arr[index - 1] > el);
  if (smallest === undefined) return arr[0]; // First element
  return smallest;
}

Метод массива find возвращает первый элемент, соответствующий заданному условию. Теперь давайте настроим эту реализацию, чтобы найти n-й наименьший элемент.

function findNthSmallest(arr = [], n = 0) {
  let smallest = arr.find((el, index) => arr[index - 1] > el);
  if (smallest === undefined) {
    smallest = arr[0]; // First element
  }
  if (n === 0) return smallest;
  let nthIndex = arr.indexOf(smallest) + n;
  if (nthIndex >= arr.length) {
    nthIndex -= arr.length; // Since array is rotated
  }
  return arr[nthIndex] > smallest ? arr[nthIndex] : undefined;
}

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

Решение 2. Решение для двоичного поиска

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

function smallest(arr = [], low, high) {
  if (low > high) return arr[0];
  if (low === high) return arr[low];
  const mid = Math.floor((low + high) / 2);
  if (mid < high && arr[mid] > arr[mid + 1]) {
    return arr[mid + 1];
  }
  if (mid > low && arr[mid] < arr[mid - 1]) {
    return arr[mid];
  }
  if (arr[high] > arr[mid]) {
    // go left
    return smallest(arr, low, mid - 1);
  }
  // else go right (since it's rotated)
  return smallest(arr, mid + 1, high);
}
function nthSmallest(arr = [], n = 0) {
  const small = smallest(arr, 0, arr.length - 1);
  if (n === 0) return small;
  let nthIndex = arr.indexOf(small) + n;
  if (nthIndex >= arr.length) {
    nthIndex -= arr.length; // Since array is rotated
  }
  return arr[nthIndex] > small ? arr[nthIndex] : undefined;
}

Ну вот!

Пожалуйста, оставьте комментарий ниже, если у вас есть другое решение, или просто какой-то общий отзыв. Спасибо за чтение!