💡Задача "Поиск в повернутом отсортированном массиве"

Условие: дан массив, сдвинутый относительно опорного элемента, который неизвестен ( массив после сдвига относительно опорного элемента имеет следующий вид: [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]])

Массив [0,1,2,4,5,6,7], имея опорный элемент 3, будет выглядеть следующим образом: [4,5,6,7,0,1,2]. 

Необходимо осуществить поиск целевого элемента в сдвинутом массиве, определив его индекс, или же вывести -1 при его отсутствии. 

Решение должно быть за O(log n) по времени. 

Пример:

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

Вывод: 4

Ввод: nums = [4,5,6,7,0,1,2], target = 3

Вывод: -1

Решение:

В этой задаче используется модифицированный бинарный поиск.

Подход

Нужно дойти до среднего элемента, а затем проверить, отсортирована ли левая часть от средних элементов или нет.

Если самый первый элемент слева меньше среднего элемента, то левая часть отсортирована, иначе нет.

Если левая часть не отсортирована, то можно гарантировать, что правая часть отсортирована.

Если мы знаем, что левая часть отсортирована и наш элемент может находиться в левой части, то мы отбрасываем правую часть, переходим к левой части и находим ключ, иначе проделываем тот же процесс для правой части.

Временная сложность:

O(logn)

Пространственная сложность:

O(1)

Код:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(a, key) {

    let low = 0, high = a.length - 1;

while(low<=high){

      let mid = Math.floor((low + high)/2);

      if(a[mid] == key) return mid;

//If left part sorted

   if(a[low] <= a[mid]){

      if(key >= a[low] && key < a[mid])

            high = mid - 1;
      else
            low = mid + 1;
     
  }

//If right part sorted
else{
        
    if(key > a[mid] && key <= a[high]) 

        low = mid + 1;
    else 
        high = mid - 1;
    
}

}
 return -1;   
};