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

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

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

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

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

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

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

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

Дан повернутый отсортированный массив nums и целое число target, верните индекс target в массиве nums или -1, если такого элемента нет.

Можно считать, что все элементы в отсортированном повернутом массиве nums уникальны. Тривиальное решение работает за O(n), можете ли вы написать алгоритм, который работает за O(log n)?

Примеры:

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

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

// Третий пример ✅
Input: nums = [1], target = 0
Output: -1
Объяснение: Массив содержит только один элемент, и это не целевой элемент.

// Четвертый пример ✅
Input: nums = [1, 3], target = 3
Output: 1
Объяснение: Элемент 3 находится в позиции с индексом 1.

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

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

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

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

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

function search(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === target) {
      return i;
    }
  }
  
  return -1;
}

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

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

✅ Гарантированно находит индекс target, если он существует

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

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

Решение 2: Одноэтапный модифицированный бинарный поиск 🚀

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

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

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

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

✅ Решает задачу за один проход

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

Решение 3: Двухэтапный подход: поиск точки поворота, затем бинарный поиск 🔧

function search(nums, target) {
  // Находим индекс минимального элемента (точку поворота)
  function findPivot(nums) {
    let left = 0;
    let right = nums.length - 1;
    
    if (nums[left] < nums[right]) {
      return 0; // Массив не был повернут
    }
    
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      
      if (nums[mid] > nums[right]) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    
    return left; // Индекс минимального элемента
  }
  
  // Стандартный бинарный поиск в отсортированном массиве
  function binarySearch(nums, left, right, target) {
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (nums[mid] === target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return -1;
  }
  
  const pivotIndex = findPivot(nums);
  
  // Определяем, в какой части массива искать целевой элемент
  if (nums[pivotIndex] <= target && target <= nums[nums.length - 1]) {
    // Ищем в правой отсортированной части
    return binarySearch(nums, pivotIndex, nums.length - 1, target);
  } else {
    // Ищем в левой отсортированной части
    return binarySearch(nums, 0, pivotIndex - 1, target);
  }
}

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

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

✅ Разбивает задачу на два более простых шага

✅ Использует стандартный бинарный поиск после нахождения точки поворота

❌ Требует дополнительного прохода по массиву

❌ Более сложная реализация с двумя вспомогательными функциями

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

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

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

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

✅ Оптимизирован для работы с особыми случаями

✅ Использует альтернативный подход к определению части массива для поиска

❌ Немного сложнее для понимания из-за более сложной логики условий

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

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

1. В повернутом отсортированном массиве всегда хотя бы одна половина (левая или правая от среднего элемента) является отсортированной.
2. Мы можем определить, какая половина отсортирована, сравнивая средний элемент с левым или правым.
3. Зная, какая половина отсортирована, мы можем проверить, находится ли target в этой отсортированной половине, используя простое сравнение с границами.
4. На основе этой проверки мы сужаем область поиска либо к отсортированной половине, либо к другой половине, которая может содержать точку поворота.

Этот подход позволяет эффективно применять принцип бинарного поиска, сокращая область поиска вдвое на каждой итерации.

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

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

   • 🚀 Одноэтапный модифицированный бинарный поиск - наиболее эффективное решение
   • 📝 Двухэтапный подход может быть проще для понимания, но менее оптимален
   • 🧮 Важно понимать структуру повернутого отсортированного массива

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

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

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

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

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

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

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

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

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

Шаг 3: mid = (4 + 4) / 2 = 4
nums[mid] = nums[4] = 0, target = 0
nums[mid] = target, поэтому возвращаем mid = 4

Результат: 4 (индекс элемента 0 в массиве)

Оптимизации

Раннее обнаружение отсутствия поворота

function search(nums, target) {
  // Если массив не повернут, используем стандартный бинарный поиск
  if (nums[0] <= nums[nums.length - 1]) {
    return binarySearch(nums, 0, nums.length - 1, target);
  }
  
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    }
    
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
  
  // Стандартный бинарный поиск
  function binarySearch(nums, left, right, target) {
    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      
      if (nums[mid] === target) {
        return mid;
      } else if (nums[mid] < target) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
    
    return -1;
  }
}

Оптимизация для случая, когда массив содержит повторы

function search(nums, target) {
  let left = 0;
  let right = nums.length - 1;
  
  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    
    if (nums[mid] === target) {
      return mid;
    }
    
    // Обработка случая с возможными повторениями
    if (nums[left] === nums[mid]) {
      left++;
      continue;
    }
    
    if (nums[left] <= nums[mid]) {
      if (nums[left] <= target && target < nums[mid]) {
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    } else {
      if (nums[mid] < target && target <= nums[right]) {
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }
  }
  
  return -1;
}

Сравнение с обычным бинарным поиском

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

Ключевое отличие нашего модифицированного алгоритма:

1. Мы определяем, какая половина массива отсортирована.
2. Проверяем, может ли целевой элемент находиться в отсортированной половине.
3. На основе этой проверки выбираем, в какой половине продолжать поиск.

Этот подход сохраняет логарифмическую сложность бинарного поиска, адаптируя его к структуре повернутого массива.

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

Почему наш алгоритм всегда находит правильный ответ?

1. Свойство отсортированного повернутого массива: В любом повернутом отсортированном массиве хотя бы одна из двух половин (относительно средней точки) является отсортированной.

   • Доказательство: Если точка поворота находится в левой половине, то правая половина полностью отсортирована. Если точка поворота находится в правой половине или отсутствует, то левая половина полностью отсортирована.

2. Корректность сужения области поиска: На каждой итерации мы проверяем, находится ли целевой элемент в отсортированной половине. Если да, мы ограничиваем поиск этой половиной; если нет, мы ищем в другой половине.

   • Если target находится в массиве, он всегда будет включен в сужающуюся область поиска.
   • Если target не находится в массиве, в конечном итоге область поиска станет пустой (left > right), и мы вернем -1.

3. Завершение алгоритма: Бинарный поиск всегда завершается, потому что на каждой итерации мы уменьшаем размер области поиска минимум вдвое.

Заключение

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

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

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