Search for a command to run...
How many times a sorted array was rotated
Try your own input
Change the array and replay the algorithm from step one.
Current step
A sorted array rotated k times puts its smallest element at index k. So counting the rotations is the same as finding the index of the minimum.
Binary Search
1function findKRotation(nums) {2 let low = 0, high = nums.length - 1;3 let ans = Infinity;//n: 8low: 0high: 7ans: ∞index: -14 let index = -1;5 6 while (low <= high) {7 const mid = Math.floor((low + high) / 2);8 9 // Range already sorted — its first element wins10 if (nums[low] <= nums[high]) {11 if (nums[low] < ans) {12 index = low;13 ans = nums[low];14 }15 break;16 }17 18 // Left half sorted — its first element is a candidate19 if (nums[low] <= nums[mid]) {20 if (nums[low] < ans) {21 index = low;22 ans = nums[low];23 }24 low = mid + 1;25 }26 // Otherwise the pivot is at or left of mid27 else {28 if (nums[mid] < ans) {29 index = mid;30 ans = nums[mid];31 }32 high = mid - 1;33 }34 }35 return index;36}