Find Number of Rotations in a Sorted Array Using Binary Search in DSA

Introduction

The Find Number of Rotations in a Sorted Array problem is a very common DSA interview question and usually comes right after questions about rotated arrays.

In simple words, this problem asks you to find how many times a sorted array has been rotated.

Real-World Meaning of Number of Rotations

Imagine a circular dial with numbers written in increasing order:

0 1 2 3 4 5 6

If the dial is rotated, the order looks different, but the smallest number shows how many steps the dial was rotated.

In the same way, in a rotated sorted array, the position of the minimum element tells us the number of rotations.

What Does “Number of Rotations” Mean?

A sorted array rotated k times means:

• The array was shifted k positions to the right (or left, depending on definition)

• The relative order of elements remains the same

Example

Original: [1, 2, 3, 4, 5]
Rotated:  [3, 4, 5, 1, 2]

Here, the array is rotated 2 times.

Key Observation (Very Important)

The number of rotations in a sorted array is equal to:

The index of the minimum element

Once we find the minimum element efficiently, the problem is solved.

Problem Statement

You are given a rotated sorted array with unique elements. Find the number of rotations.

Example

Array: [15, 18, 2, 3, 6, 12]
Output: 2

Explanation:

• The smallest element is 2

• It appears at index 2

• So, the array is rotated 2 times

Before vs After Understanding

Linear Scan (Before)

• Check every element

• Find the smallest

• Return its index

Works, but slow for large arrays.

Binary Search (After)

• Use array properties

• Reduce search space by half

• Find minimum efficiently

Why Binary Search Works Here

In a rotated sorted array:

• One half is always sorted

• The minimum element lies in the unsorted half

Binary search helps us directly move toward that half.

What Interviewers Are Actually Testing

Interviewers want to see:

• Do you understand rotation logic?

• Can you reuse binary search ideas?

• Can you convert observation into code?

This problem tests pattern recognition, not memorization.

Key Idea (Very Simple)

• If middle element is greater than the rightmost element

  • Minimum is on the right side

• Else

  • Minimum is on the left side or at mid

The index of that minimum element is the answer.

Step-by-Step Logic

1. Set low = 0, high = n - 1

2. Find mid

3. Compare arr[mid] with arr[high]

4. If arr[mid] > arr[high], move low to mid + 1

5. Else, move high to mid

6. Continue until low == high

Return low as the number of rotations.

Dry Run Example

Array: [15, 18, 2, 3, 6, 12]

low	high	mid	comparison	move
0	5	2	2 < 12	left
0	2	1	18 > 2	right
2	2	-	stop	answer

Answer = 2 rotations

One-Line Logic Before Code

Find the index of the smallest element using binary search.

Code Implementation (C++)

int countRotations(vector<int>& nums) {
    int low = 0, high = nums.size() - 1;

    while (low < high) {
        int mid = low + (high - low) / 2;
        if (nums[mid] > nums[high])
            low = mid + 1;
        else
            high = mid;
    }
    return low;
}

Common Beginner Mistakes

• Thinking rotations need to be counted manually

• Using linear scan in interviews

• Confusing rotation count with array length

Time and Space Complexity

• Time Complexity: O(log n)

• Space Complexity: O(1)

Easy Summary (Explain Like I’m 10)

If a sorted list is rotated, the smallest number shows where the rotation started. By finding where the smallest number is using binary search, we immediately know how many times the array was rotated.

Summary

Finding the number of rotations in a sorted array using binary search is a clean and efficient problem that builds directly on rotated array concepts. By observing that the rotation count equals the index of the minimum element, you can solve this problem in logarithmic time. This approach is frequently tested in interviews and strengthens your understanding of rotated sorted array patterns in DSA.