Проблема
Имеется целочисленный массив nums, отсортированный по возрастанию (с четкими значениями).
Перед передачей в вашу функцию nums, возможно, повернут на неизвестный поворотный индекс k (1 <= k < nums.length) так, что результирующий массив имеет вид nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1] (0-индексированный). Например, [0,1,2,4,5,6,7] может быть повернут на индекс поворота 3 и стать [4,5,6,7,0,1,2].
Учитывая массив nums после возможного поворота и целое число target, верните индекс target, если он есть в nums, или -1, если его нет в nums.
Вы должны написать алгоритм со сложностью выполнения O(logn).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Example 3:
Input: nums = [1], target = 0
Output: -1
Source: Leetcode
Ограничения:
1 <= nums.length <= 5000
-104 <= nums[i] <= 104
All values of nums are unique.
nums is an ascending array that is possibly rotated.
-104 <= target <= 104
Как решить эту интересную задачу?
Если отсортированный массив не вращается, то найти целевое значение с помощью алгоритма двоичного поиска несложно. Ведь мы знаем, что целевое значение будет находиться где-то между первым и последним элементом массива. Но если мы повернем массив, он перестанет быть отсортированным, верно?
Читайте больше в нашем блоге Foolish Hungry dot com … 🙂