Binary Search - DSA: Find Out How Many Times Array Has Been Rotated

1. Introduction and Problem Statement

When dealing with sorted arrays that have undergone a number of circular rotations, determining the count of rotations is a classic algorithmic puzzle. In this chapter, we explore how to find the rotation count of a sorted array containing unique numbers using an extension of the Binary Search algorithm.

• Status Quo (Sorted Array): 1, 2, 3, 4, 5 (Rotated 0 times)
• Rotated Array: 3, 4, 5, 1, 2 (Rotated 3 times)

2. Core Mental Model: The Rotation-Minimum Relationship

The fundamental insight required to solve this problem is recognizing a direct mathematical property of rotated sorted arrays: The number of times a sorted array has been rotated to the right is equal to the index of its minimum element.

Real-Life Analogy: The Combination Lock

Analogy: Imagine a circular bicycle combination lock or a vault dial. If the numbers 0, 1, 2, 3, 4, 5 are initially aligned in order at the top (0 rotations), turning the dial to the right shifts the sequence. If the number 1 (our anchor minimum) ends up shifted to the 3rd position, simply looking at where position 1 landed tells you exactly how many clicks (rotations) the dial underwent.

Thus, finding the rotation count boils down to finding the index of the minimum element in the rotated sorted array.

3. Connecting to Previous Problems

In the preceding lesson (BS-6. Find Minimum in Rotated Sorted Array), we established how to locate the minimum element in $O(\log N)$ time complexity using Binary Search.

• Key realization: We do not need a brand new algorithm. We can take the exact logic used to find the minimum value and augment it to track the index where that minimum value is found.
• The Answer is the Index: While the previous problem returned answer (the minimum value itself), this problem returns index (the position of that minimum value).

4. Naive Approach vs. Optimal Binary Search Approach

Naive Linear Search Approach

• Strategy: Iterate through the entire array from left to right, comparing each element with its predecessor or keeping track of the minimum value and its index.
• Time Complexity: $O(N)$ because we inspect every single element.
• Space Complexity: $O(1)$.
• Limitation: This does not leverage the sorted nature of the partitions, making it suboptimal for large datasets where $O(\log N)$ is expected.

Optimal Binary Search Approach

• Strategy: Use the binary search space-reduction technique. In a rotated sorted array, at least one half (left or right of mid) is always sorted.
• Time Complexity: $O(\log N)$.
• Space Complexity: $O(1)$.

5. Step-by-Step Code Evolution

Let's examine how the minimum-finding code transitions into the rotation-counting code by tracking indices alongside values.

Step 5.1: The Minimum-Finding Logic (Review)

int findMin(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;
    int ans = INT_MAX;
    while (low <= high) {
        int mid = low + (high - low) / 2;
        // If left part is sorted, pick leftmost and eliminate left half
        if (nums[low] <= nums[mid]) {
            ans = min(ans, nums[low]);
            low = mid + 1;
        } else { // Right part is sorted
            ans = min(ans, nums[mid]);
            high = mid - 1;
        }
    }
    return ans;
}

Step 5.2: Augmenting Code to Track Indices

To convert this into our target solution, whenever ans is updated with a smaller value, we simultaneously record the index (low or mid) where that value was found.

#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

class Solution {
public:
    int findKRotation(vector<int>& arr) {
        int low = 0, high = arr.size() - 1;
        int ans = INT_MAX;
        int index = -1; // Tracks the index of the minimum element

        while (low <= high) {
            int mid = low + (high - low) / 2;

            // Optimization: If the search space is already sorted,
            // the first element is the minimum of this subsegment.
            if (arr[low] <= arr[high]) {
                if (arr[low] < ans) {
                    ans = arr[low];
                    index = low;
                }
                break;
            }

            // If left part is sorted
            if (arr[low] <= arr[mid]) {
                if (arr[low] < ans) {
                    ans = arr[low];
                    index = low; // Record index of low
                }
                low = mid + 1; // Eliminate left sorted half
            } 
            // If right part is sorted
            else {
                if (arr[mid] < ans) {
                    ans = arr[mid];
                    index = mid; // Record index of mid
                }
                high = mid - 1; // Eliminate right sorted half
            }
        }
        return index; // The index of the minimum element = rotation count
    }
};

6. Complete Flow Walkthrough

Let's trace the algorithm with our example array: arr = [3, 4, 5, 1, 2] ($N = 5$).

Initial State:
low = 0, high = 4, ans = INF, index = -1

• Iteration 1:

  • mid = 0 + (4 - 0) / 2 = 2 (arr[2] = 5)
  • Check left sorted half: arr[low] <= arr[mid] -> arr[0] <= arr[2] (3 <= 5 -> True).
  • Compare arr[low] (3) with ans (INF). 3 < INF, so:
    • ans = 3
    • index = 0 (current low)
  • Eliminate left half: low = mid + 1 -> low = 3.

• Iteration 2:

  • low = 3, high = 4
  • mid = 3 + (4 - 3) / 2 = 3 (arr[3] = 1)
  • Check left sorted half: arr[3] <= arr[3] (1 <= 1 -> True).
  • Compare arr[low] (arr[3] = 1) with ans (3). 1 < 3, so:
    • ans = 1
    • index = 3 (current low)
  • Eliminate left half: low = mid + 1 -> low = 4.

• Iteration 3:

  • low = 4, high = 4
  • mid = 4 + (4 - 4) / 2 = 4 (arr[4] = 2)
  • Check left sorted half: arr[4] <= arr[4] (2 <= 2 -> True).
  • Compare arr[low] (arr[4] = 2) with ans (1). 2 < 1 is False (no update).
  • Eliminate left half: low = mid + 1 -> low = 5.
  • Loop terminates (low > high).

• Final Return: Returns index = 3. The array has been rotated 3 times.

7. Handling Edge Cases and Variations

8. Summary and Key Takeaways

• Equivalence Principle: Finding the number of times a sorted array has been rotated is identical to finding the index of the minimum element.
• Time Complexity: Optimal binary search approach runs in $O(\log N)$ time, significantly faster than an $O(N)$ linear scan.
• Space Complexity: Operates in $O(1)$ auxiliary space.
• Index Tracking: Simply capture and update an index variable alongside the minimum value whenever a lower value is encountered at low or mid.
• Subsegment Sorted Check: Identifying which half of the array is sorted (arr[low] <= arr[mid]) allows us to safely harvest the minimum and discard that half.
• Sequential Learning: Mastering foundational problems like Find Minimum in Rotated Sorted Array directly unlocks solutions to derivative problems like rotation counting.
• Extension to Duplicates: Arrays with duplicate elements require shrinking boundary pointers (low++, high--) to handle ambiguity, mirroring Part 2 variations of rotated search problems.