Rotation Count in Rotated Sorted Array

altruistcoder · altruistcoder · commit 0b0cdf3d74df · 2019-08-24T21:43:03.000+05:30
diff --git a/README.md b/README.md
@@ -193,3 +193,7 @@ This is a repository containing various C++ Programs to understand the basic con
 
   C++ Code for checking whether two given strings are anagrams of each other.
 
+
+* [Rotation Count in a Rotated Sorted Array](https://github.com/altruistcoder/Data-Structures/blob/master/rotation_count.cpp):
+
+  C++ Code for finding the rotation count in a rotated sorted array.
diff --git a/rotation_count.cpp b/rotation_count.cpp
@@ -0,0 +1,30 @@
+#include<bits/stdc++.h>
+using namespace std;
+
+int countRotations(int a[], int low, int high)
+{
+    if (high < low)
+        return 0;
+    if (high == low)
+        return low;
+    int mid=low+(high-low)/2;
+    if (mid < high && a[mid+1] < a[mid])
+       return (mid+1);
+    if (mid > low && a[mid] < a[mid-1])
+       return mid;
+    if (a[high] > a[mid])
+       return countRotations(a, low, mid-1);
+    return countRotations(a, mid+1, high);
+}
+
+int main()
+{
+    int n, a[100];
+    cout<<"Enter the size of the array: ";
+    cin>>n;
+    cout<<"Enter the elements of the array: ";
+    for(int i=0;i<n;i++)
+        cin>>a[i];
+    cout<<"The rotation count of the given rotated sorted array is: "<<countRotations(a, 0, n-1);
+    return 0;
+}
