Поиск в вращённом отсортированном массиве

Дан отсортированный массив целых чисел nums, который был вращён на некоторое количество мест, и целое число target. Напишите функцию, которая находит индекс target в этом массиве. Если target не найден в массиве, функция должна вернуть -1.

Массив может быть, например, [4, 5, 6, 7, 0, 1, 2] — это тот же массив [0, 1, 2, 4, 5, 6, 7], но вращённый на 4 позиции.

Пример:

  1. Вход: nums = [4, 5, 6, 7, 0, 1, 2], target = 0 Выход: 4

    Объяснение: 0 находится на индексе 4 в массиве.

  2. Вход: nums = [4, 5, 6, 7, 0, 1, 2], target = 3 Выход: -1

    Объяснение: 3 не присутствует в массиве.

  3. Вход: nums = [1], target = 0 Выход: -1

    Объяснение: 0 не присутствует в массиве.

fun searchInRotatedArray(nums: IntArray, target: Int): Int {
    var left = 0
    var right = nums.size - 1

    while (left <= right) {
        val mid = left + (right - left) / 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
}

Объяснение:

  1. Инициализация: Устанавливаем left в 0 и right в nums.size - 1.
  2. Бинарный поиск:
    • Находим средний индекс mid.
    • Если значение в nums[mid] равно target, возвращаем mid.
    • Определяем, какая часть массива отсортирована:
      • Если левая половина отсортирована (nums[left] <= nums[mid]), проверяем, находится ли target в этой части. Если да, сужаем диапазон поиска до левой половины (right = mid - 1). Иначе, ищем в правой половине (left = mid + 1).
      • Если правая половина отсортирована, проверяем, находится ли target в этой части. Если да, сужаем диапазон поиска до правой половины (left = mid + 1). Иначе, ищем в левой половине (right = mid - 1).
  3. Возвращение результата: Если target найден, возвращаем его индекс. Если нет, возвращаем -1.