Поиск минимума в отсортированном повернутом массиве: разбор задачи

Почему эта задача важна?

Задача "Поиск минимума в отсортированном повернутом массиве" позволяет оценить:

• 🧠 Глубокое понимание алгоритма бинарного поиска и его модификаций
• ⚡ Навыки адаптации классических алгоритмов к нестандартным условиям
• 🎯 Умение анализировать структуру массива и использовать его свойства
• 🔍 Способность разрабатывать решения с логарифмической сложностью

Постановка задачи

Формулировка:

Дан массив длины n, который изначально был отсортирован по возрастанию. Затем он был повернут от 1 до n раз. Например, массив nums = [1,2,3,4,5,6] мог стать:

• [3,4,5,6,1,2], если его повернули 4 раза
• [1,2,3,4,5,6], если его повернули 6 раз

Обратите внимание, что поворот массива 4 раза перемещает последние четыре элемента массива в начало. Поворот массива 6 раз возвращает исходный массив.

Предполагая, что все элементы в повернутом отсортированном массиве nums уникальны, верните минимальный элемент этого массива.

Решение, работающее за время O(n), тривиально. Можете ли вы написать алгоритм, который работает за время O(log n)?

Примеры:

// Первый пример ✅
Input: nums = [3, 4, 5, 1, 2]
Output: 1
Объяснение: Исходный массив был [1,2,3,4,5] и был повернут 3 раза.

// Второй пример ✅
Input: nums = [4, 5, 6, 7, 0, 1, 2]
Output: 0
Объяснение: Исходный массив был [0,1,2,4,5,6,7] и был повернут 4 раза.

// Третий пример ✅
Input: nums = [11, 13, 15, 17]
Output: 11
Объяснение: Исходный массив был [11,13,15,17] и был повернут 4 раза (или можно сказать, не был повернут вообще).

Ограничения:

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• Все значения в nums уникальны
• nums - отсортированный и повернутый массив

Подходы к решению

Решение 1: Линейный поиск (наивный подход) 🔍

function findMin(nums) {
  let min = nums[0];
  
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < min) {
      min = nums[i];
    }
  }
  
  return min;
}

Анализ решения:

✅ Простая реализация и понятная логика

✅ Гарантированно находит минимальный элемент

❌ Временная сложность O(n), не соответствует требованию задачи

❌ Не использует свойства отсортированного повернутого массива

Решение 2: Классический бинарный поиск (модифицированный) 🚀

function findMin(nums) {
  let left = 0;
  let right = nums.length - 1;
  
  // Если массив не был повернут или был повернут полностью
  if (nums[left] < nums[right]) {
    return nums[left];
  }
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // Если средний элемент больше правого,
    // то минимум находится в правой части
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } 
    // Иначе минимум находится в левой части
    // или средний элемент является минимумом
    else {
      right = mid;
    }
  }
  
  // По окончании цикла left = right и указывает на минимальный элемент
  return nums[left];
}

Характеристики:

✅ Оптимальная временная сложность O(log n)

✅ Эффективно использует свойства отсортированного повернутого массива

✅ Минимальное количество сравнений

✅ Соответствует всем требованиям задачи

Решение 3: Бинарный поиск с использованием сравнения с первым элементом 🔧

function findMin(nums) {
  let left = 0;
  let right = nums.length - 1;
  
  // Если массив не был повернут или был повернут полностью
  if (nums[left] < nums[right]) {
    return nums[left];
  }
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // Если средний элемент больше или равен первому элементу,
    // то минимум находится в правой части
    if (nums[mid] >= nums[0]) {
      left = mid + 1;
    } 
    // Иначе минимум находится в левой части
    else {
      right = mid;
    }
  }
  
  // Проверяем особый случай, когда минимум - первый элемент
  return nums[left] < nums[0] ? nums[left] : nums[0];
}

Преимущества и недостатки:

✅ Временная сложность O(log n)

✅ Альтернативный подход к условию проверки в бинарном поиске

❌ Требует дополнительной проверки для случая, когда минимум - первый элемент

❌ Менее интуитивное условие сравнения

Решение 4: Оптимизированный бинарный поиск с ранним выходом 📊

function findMin(nums) {
  // Особые случаи
  if (nums.length === 1) return nums[0];
  if (nums.length === 2) return Math.min(nums[0], nums[1]);
  if (nums[0] < nums[nums.length - 1]) return nums[0];
  
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    // Проверяем, является ли средний элемент минимумом
    // Сравниваем с соседними элементами
    if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1]) {
      return nums[mid];
    }
    
    // Если средний элемент больше правого,
    // то минимум находится в правой части
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } 
    // Иначе минимум находится в левой части
    else {
      right = mid - 1;
    }
  }
  
  // Этот возврат не должен быть достигнут при правильных входных данных
  return nums[left];
}

Особенности:

✅ Временная сложность O(log n)

✅ Содержит оптимизации для особых случаев

✅ Может найти минимум раньше, чем закончится бинарный поиск

❌ Требует дополнительных проверок граничных условий

❌ Более сложная реализация

Интуиция за алгоритмом бинарного поиска в повернутом массиве

Ключевая идея алгоритма заключается в следующем:

1. В отсортированном повернутом массиве всегда существует точка поворота, где заканчивается одна отсортированная последовательность и начинается другая.
2. Минимальный элемент массива находится в этой точке поворота.
3. Мы можем использовать бинарный поиск для нахождения этой точки, сравнивая средний элемент с правым элементом:
   • Если nums[mid] > nums[right], то минимум находится в правой части.
   • Если nums[mid] <= nums[right], то минимум находится в левой части (включая mid).

Такой подход всегда сужает область поиска вдвое и гарантированно находит минимальный элемент.

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Модифицированный бинарный поиск - оптимальный подход
   • 📝 Главное - правильно определить условие для сужения области поиска
   • 🧮 Важно понимать структуру повернутого отсортированного массива

2. Важные моменты:

   • 📝 Обработка случая, когда массив не был повернут или был повернут полностью
   • 🔄 Правильное обновление границ поиска
   • 📊 Корректное условие остановки цикла

Распространённые ошибки

1. 🤦‍♂️ Неправильное условие сравнения в бинарном поиске
2. 😅 Забывание обработать случай, когда массив не был повернут
3. 🐛 Неверное обновление границ поиска, что может привести к пропуску минимального элемента

Визуализация алгоритма бинарного поиска

Рассмотрим пример массива [4, 5, 6, 7, 0, 1, 2]:

Начальное состояние:
nums = [4, 5, 6, 7, 0, 1, 2], left = 0, right = 6

Шаг 1: mid = (0 + 6) / 2 = 3
nums[mid] = nums[3] = 7, nums[right] = nums[6] = 2
7 > 2, поэтому минимум находится в правой части
Обновляем left = mid + 1 = 4
Новые границы: left = 4, right = 6

Шаг 2: mid = (4 + 6) / 2 = 5
nums[mid] = nums[5] = 1, nums[right] = nums[6] = 2
1 < 2, поэтому минимум находится в левой части (включая mid)
Обновляем right = mid = 5
Новые границы: left = 4, right = 5

Шаг 3: mid = (4 + 5) / 2 = 4
nums[mid] = nums[4] = 0, nums[right] = nums[5] = 1
0 < 1, поэтому минимум находится в левой части (включая mid)
Обновляем right = mid = 4
Новые границы: left = 4, right = 4

Теперь left = right = 4, цикл завершается
Минимальный элемент: nums[4] = 0

Оптимизации

Проверка отсутствия поворота в начале

function findMin(nums) {
  // Если массив не был повернут или был повернут полностью
  if (nums[0] < nums[nums.length - 1]) {
    return nums[0];
  }
  
  let left = 0;
  let right = nums.length - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] > nums[right]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return nums[left];
}

Обработка массивов малой длины

function findMin(nums) {
  const n = nums.length;
  
  // Проверка для массивов длиной 1 или 2
  if (n === 1) return nums[0];
  if (n === 2) return Math.min(nums[0], nums[1]);
  
  // Проверка отсутствия поворота
  if (nums[0] < nums[n - 1]) {
    return nums[0];
  }
  
  let left = 0;
  let right = n - 1;
  
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    
    // Если нашли точку поворота
    if (mid > 0 && nums[mid] < nums[mid - 1]) {
      return nums[mid];
    }
    
    if (nums[mid] >= nums[0]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }
  
  return nums[left];
}

Математическое обоснование корректности

Почему сравнение средний элемент > правый работает для нахождения минимума в повернутом массиве?

Рассмотрим все возможные случаи:

1. Если массив не был повернут, то первый элемент всегда минимальный.
2. Если массив был повернут, то существует точка поворота, где минимум.
3. Элементы слева от точки поворота всегда больше или равны первому элементу массива.
4. Элементы справа от точки поворота всегда меньше первого элемента массива.

Когда мы сравниваем nums[mid] с nums[right]:

• Если nums[mid] > nums[right], это означает, что точка поворота находится между mid и right, поэтому минимум в правой части.
• Если nums[mid] <= nums[right], это означает, что или mid - минимум, или точка поворота находится слева от mid, поэтому минимум в левой части (включая mid).

Заключение

При решении задачи "Поиск минимума в отсортированном повернутом массиве" важно помнить:

• 🤹‍♂️ Бинарный поиск - идеальный алгоритм для этой задачи, но требует модификации
• 📊 Ключевое наблюдение: сравнение среднего элемента с правым позволяет определить, в какой части находится минимум
• 🧠 Понимание структуры повернутого массива критически важно для разработки эффективного решения

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