Find the starting point of a sorted rotated array.

Given an ascending sorted rotated array, we aim to get the starting point of the array (the smallest element in the input array). Let us discuss this with an example.

// Input = {3, 4, 5, 6, 7, 8, 0, 1, 2}
// Output = 6 // Index of the starting point "0".
Sorted rotated array starting from ‘0’ which is at index 6.

We use binary search to find the starting point of the sorted array. Let us see how this works.

Here the mid element 7 is greater than 6 which follow the ascending order. Right half of the elements not following ascending order rule so our starting point would be in that half.
In the second half the middle element 0 which is not greater than its previous element ‘8’. So, our output is middle index which is 6.

As we are using binary search to solve this problem, the runtime of this algorithm is O(logN). Let us see the code for this approach.

int findStartOfRotatedArray(int arr[], int start, int end)
{
    int mid = (start + end) / 2;
    if (mid == 0)
    {
        return mid;
    }
    // Check middle element following ascending order rule.
    if (arr[mid - 1] > arr[mid])
    {
        return mid;
    }
    // Check left subarray following ascending order rule.
    if (arr[mid] > arr[start])
    {
        return findStartOfRotatedArray(arr, mid + 1, end);
    }
    // process right subarray.
    else
    {
        return findStartOfRotatedArray(arr, start, mid - 1);
    }
}

We used recursion to solve this problem, even we can solve this using iteration. Full code with main function is as following.

// Output
6

It is all about finding a starting point of a sorted rotated integer array in binary search approach. If you know any better approach to solve this problem, please let our readers know by commenting here below. Happy Learning!.