## Problem Statement

You are given a sorted array. However, there is a problem. Someone just rotated the sorted array by K spaces and we do not know the value of K. Write a program to find the value of K by which the array is rotated. As the array has millions of numbers, it would be good to have a solution which takes minimal time.## Approach to Find the Point of Rotation

**Brute Force**Let us try out my favorite approach, the Brute Force Method. It is quite simple, below are the steps:

- Start traversing the array from the beginning
- There will be a index in the array where the value stored at the index will be smaller than the value at the previous index.
- Return the index.

public static void bruteForce(int[] A) { for (int i = 1; i < A.length; i++) { if(A[i] < A[i-1]){ System.out.println(A[i]); break; } } }Analysis: As we traverse the whole array, the time taken is linear to the input size i.e. O(N). It requires constant space to maintain loop counters etc.

**Efficient Solution**The above solution is great, however, the problem says efficient solution, and here is one. Remember our best friend, Binary Search? If we notice, there is just one index in the complete array, where the numbers start decreasing.

- Each number in the left of this point is greater than the last element in the array.
- Each element in the right of this point is smaller than the last element in the array.
- Lets find a middle index M in the range [L .. R] and probe it in comparison to the last element of the array
- If the element is smaller than the last,
- the point of rotation definitely lies in the left of the middle element
- Hence, redefine the range for probing [L .. M - 1]

- Else
- The point of rotation certainly lies in the right of the middle element
- Hence, redefine the range for probing [M+1, L]

- Re-calculate the M and repeat the probing.
- Terminate the loop when start is not less than or equal to end

public static void findRotationPoint(int[] A) { int start = 0, end = A.length - 1, mid; mid = start + (end - start) / 2; int last = A[A.length - 1]; while (start <= end) { if (A[mid] > last) { start = mid + 1; } else if (A[mid] < last) { end = mid - 1; } else break; mid = start + (end - start) / 2; } System.out.println(A[mid]); }Analysis: As the code is a vanilla Binary Search, it has logarithmic running time O(logN). The space requirements remain same as constant O(1)