⬅ Previous Topic
Minimum in Rotated Sorted ArrayNext Topic ⮕
Search Single Element in Sorted Array⬅ Previous Topic
Minimum in Rotated Sorted ArrayNext Topic ⮕
Search Single Element in Sorted ArrayTopic Contents
Given a sorted and rotated array of distinct integers, your task is to determine the number of times the array has been rotated.
Your goal is to find the index of the smallest element in the array, as this index represents the number of rotations.
If the array is empty, return -1
.
start = 0
, end = n - 1
.start ≤ end
:arr[start] ≤ arr[end]
, the subarray is already sorted, so return start
.mid = start + (end - start) / 2
.prev = (mid - 1 + n) % n
and next = (mid + 1) % n
.arr[mid] ≤ arr[prev]
and arr[mid] ≤ arr[next]
, return mid
.arr[mid] ≥ arr[start]
, search in the right half: start = mid + 1
.end = mid - 1
.public class RotationCountFinder {
public static int findRotationCount(int[] arr) {
int n = arr.length;
int start = 0, end = n - 1;
while (start <= end) {
if (arr[start] <= arr[end]) return start; // Sorted, minimum at start
int mid = start + (end - start) / 2;
int next = (mid + 1) % n;
int prev = (mid - 1 + n) % n;
if (arr[mid] <= arr[prev] && arr[mid] <= arr[next])
return mid; // Found the pivot
else if (arr[mid] >= arr[start])
start = mid + 1; // Search right
else
end = mid - 1; // Search left
}
return 0; // Not rotated
}
public static void main(String[] args) {
int[] arr = {15, 18, 2, 3, 6, 12};
System.out.println("Rotation Count: " + findRotationCount(arr));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(1) | When the array is not rotated, the first check detects it immediately. |
Average Case | O(log n) | Each iteration eliminates half the search space by applying binary search logic. |
Worst Case | O(log n) | In the worst case, the search continues until the pivot element is found using binary search. |
O(1)
Explanation: Only a constant number of variables (start, end, mid, next, prev) are used for the search.
⬅ Previous Topic
Minimum in Rotated Sorted ArrayNext Topic ⮕
Search Single Element in Sorted ArrayYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.