Find out how many times the array has been rotated || Find Lowest Element Index

[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

Leave a Comment

Your email address will not be published. Required fields are marked *