[Question] Given an integer array arr of size N, sorted in ascending order (with distinct values). Now the array is rotated between 1 to N times which is unknown. Find how many times the array has been rotated.
Example 1: Input Format: arr = [4,5,6,7,0,1,2,3] Result: 4 Explanation: The original array should be [0,1,2,3,4,5,6,7]. So, we can notice that the array has been rotated 4 times.
// TC: O(log(N))
// SC: O(1)
func findLowestNumberIndex(_ nums: [Int]) ->Int {
var low = 0
var high = nums.count - 1
var ans = Int.max
var index = -1
while low <= high {
let mid = (low + high) / 2
//search space is already sorted
//then arr[low] will always be
//the minimum in that search space:
if nums[low] <= nums[high] {
if nums[low] < ans {
index = low
ans = nums[low]
}
break
}
// If left part is sorted:
if nums[low] <= nums[mid] {
// Keep the minimum:
if nums[low] < ans {
index = low
ans = nums[low]
}
// Eliminate left half:
low = mid + 1
} else { // If right part is sorted:
// Keep the minimum:
if nums[mid] < ans {
index = mid
ans = nums[mid]
}
// Eliminate right half:
high = mid - 1
}
}
return index
}
let rotaArrayInput = [4, 5, 6, 7, 0, 1, 2, 3]
let rotaArrayOutput = findLowestNumberIndex(rotaArrayInput)
print("The minimum element index is: ", rotaArrayOutput)// 4