Поиск количества разворотов массива

count-rotations.js

/*
Поиск количества разворотов массива за O(n)
*/
function countRotations(arr) {
  var min = arr[0], minIndex = 0;
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
      minIndex = i;
    }
  }
  return minIndex;
}

/*
Поиск количества разворотов массива за Log(n)
*/
function countRotationsLog(arr, low, high) {
  // Дошли до конца, всё окей, в массиве нет поворотов
  if (high < low) return 0;
  
  // В массиве остался один элемент
  if (high == low) return low;
  
  // Но лучше написать что-то вроде
  // low + (high - low) / 2
  var mid = Math.floor((low + high) / 2);
  
  // Проверяем, является ли mid + 1 минимальным элементом
  // (например, [3, 4, 5, 1, 2])
  if (mid < high && arr[mid + 1] < arr[mid])
    return mid + 1;
  
  // Проверяем, является ли mid минимальным элементом
  if (mid > low && arr[mid] < arr[mid - 1])
    return mid;
  
  if (arr[high] > arr[mid])
    return countRotationsLog(arr, low, mid - 1);
 
  return countRotationsLog(arr, mid + 1, high);
}

console.log(countRotationsLog([2, 3, 4, 5, 1], 0, 4));
console.log(countRotations([3, 4, 5, 1, 2]));