Since the array A has sufficient space for the merged array, we can start from the end of the array A and start filling the result elements.
We compare the elements at i and j indices. We move the bigger element to the end pointed by res and decrement the corresponding index. We do this until we reach the beginning of any array. Finally we check if there any left over elements in the second array. If there are, we have to move them to the first array.
We maintain two indices; one to track the elements of resultant array (result index), and another to iterate through all the elements. While iterating through each element using second index, if we see an element which is not equal to the target element, we can copy it to the same array from the beginning, and increment the result index.
This algorithm runs in O(n) time and O(1) space complexity.
Here is the simple implementation in C++.
For example let us consider the array [12, 15, 6, 8, 10], the element 8 is found at index 3.
We can design an algorithm like this. We first check if the middle element equals the target element. If so, we return the mid.
Otherwise we check to see if the left half is sorted or right half is sorted. In any case only one portion will be sorted. We have to narrow down our search based on the range of elements which the target belongs to .
if( arr[low] <= arr[mid]) //left half is sorted
//If target lies in first half
if( s >= arr[low] && s < arr[mid] )
high = mid – 1;
low = mid + 1; // narrow down to right half
else // Right half is sorted
if( s > arr[mid] && s <= arr[high] )
low = mid + 1;
high = mid – 1;
Here is the iterative implementation of the above algorithm. This algorithm runs in O( log n ) time complexity.
For example the array [4, 5, 1, 2, 3] is (right) rotated twice.
Before proceeding to find a solution, let’s note some observations.
To find the number of rotations, we have to find the smallest element in the array. If we find the index of the smallest element in the array, that will indicate the number of rotations.
In the above example, the smallest number is 1 which is located at index ‘2’. We can easily verify that the array is rotated twice.
A simple approach could be to use a linear search to find the least number and return it’s index. This approach will obviously take O(n) time. Can we perform better than that?
Yes, it can be done by utilizing the sorted property of the array. Here is how we can do this.
Just like Binary search, we can use divide and conquer approach. We write a recursive function which will take the array, lower and upper bound as its parameters.
We first check whether the array is sorted from the beginning (not rotated). This can be done by checking if array[low] <= array[high]. If it is not rotated, we can simply return the index low.
Next we check if the middle element is the smallest element by comparing it with the previous and next elements.
If this condition is satisfied, then we return mid. One caution while calculating the next and previous indices is to consider the array boundaries. We have to assume that the array is circular.
//if mid is at 0, consider last element as previous
int prev = (mid – 1 + len) % len;
//if mid is the last element, consider next element as the first
int next = (mid + 1) % len;
Next, we check which portion is already sorted. If the left portion is properly sorted (without rotations), we search in the right half. Otherwise we search in the left half.
return findRotations(arr, mid+1, high);
return findRotations(arr, low, mid-1);
Even more simplified version of the algorithm is given below.