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".
We use binary search to find the starting point of the sorted array. Let us see how this works.
As we are using binary search to solve this problem, the runtime of this algorithm is . 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!.