If you have ever used an algorithm like Binary Search, you may have come across its advantages over the Time complexity of, let's say a linear search. We will not dive into the realms of time complexities for now.
Let us suppose, we have an Array of sorted elements such as:
int[] Arr = [0,1,2,3,4,5,6,7];
Let’s rotate this array in a clockwise manner. So, the element in the end, i.e. ‘7’, gets rotated clockwise and becomes the start element. So after the first rotation, our array now becomes,
R1: [7,0,1,2,3,4,5,6].
Let’s keep on rotating this array a couple of times, to see what happens.
R2: [6,7,0,1,2,3,4,5]
R3: [5,6,7,0,1,2,3,4]
R4: [4,5,6,7,0,1,2,3]…. and so on. If you keep rotating this array for a couple more iterations, you will reach a point where you get the initial array ‘Arr’, like the one above.
Now, let’s take a point in the rotation of the array such as R4. We can observe a certain pattern or a situation, where the elements in the array have ascended from the initial position (i.e. 4 for this array) and ascended up to ‘7’, and then there is a drop in the value after 7, where the element after 7 is 0, and then, the elements again, gradually ascend till ‘3’.
Now, let’s define a pivot element. A pivot element is an element, such that while rotating the array, it is the highest value in the array. In array R4, the PIVOT element is 7.
Steps:
After the pivot element in the array is found, we have to divide the array into two sub-arrays.
The first part of the sub-array begins from the initial element till the pivot element. (in the above case, from 4 to 7), and the second part begins from the element after the pivot, (in this case 0), till the last element(in this case, 4).
We then, apply Binary Search in both of these sub-array, and subsequently our element will be found.
I will be writing some pseudo codes on how to complete Binary Search, find the pivot element, and then find our element in the Rotated Array, in upcoming Articles.