Minimum Number in a sorted rotated array in Java
The minimum number in a sorted rotated array is a complex computer science problem that disrupts the linear order of elements. It impacts algorithm performance and scalability in software engineering domains like compiler optimization, database indexing, and robotics. Despite challenges, innovation in the following area transcends problem-solving and into mathematics and computer science. It mirrors real-world challenges in database management and robotics, fostering an appreciation for modular arithmetic and cyclic structures. Challenges fuel innovation, community engagement, and cross-disciplinary connections between computer science and mathematics.
Example1:
Input: nums = [3, 4, 1, 5, 2]
Output: 1
Explanation: By iterating through the array, we discover that 1 is the smallest element despite the rotation.
Example2:
Input: nums = [12, 17, 19, 15]
Output: 12
Explanation: By iterating through the array, we discover that 12 is the smallest element despite the rotation.
Using Naive Approach
Algorithm
Step 1: Set the minimum element as the first element.
Step 2: Traverse array from second to last.
Step 3: Update the minimum element to the current element if the current is less than the minimum.
Step 4: Return the minimum element found after traversal.
Here is an implementation of finding the minimum number in a sorted rotated array using a naive approach :
FileName:MinimumElementInRotatedSortedArray.java
public class MinimumElementInRotatedSortedArray {
static int findMin(int[] arr, int n) {
// Initialize the minimum element as the first element
int min = arr[0];
// Traverse the array to find the minimum element
for (int i = 1; i < n; i++) {
// If the current element is less than the minimum element, update the minimum element
if (arr[i] < min) {
min = arr[i];
}
}
// Return the minimum element found
return min;
}
public static void main(String[] args) {
int[] arr = {4, 5, 1, 2, 3};
System.out.println("Minimum element in arr: " + findMin(arr, arr.length));
}
}
Output:
Minimum element in arr: 1
Complexity analysis: The above approach's time complexity is O(N). To find the minimum element, the algorithm searches the entire array once, and the space complexity is O(1); regardless of the size of the input array, the algorithm only requires a fixed amount of additional space for variables.
Using Optimized Approach
Algorithm
Step 1: Check if the array has no or only one element.
Step 2: Initialize start and end indices for binary search.
Step 3: Enter a loop until the start is less than or equal to the end.
Step 4: Return the element at the start if the subarray is already sorted.
Step 5: Calculate the mid index and return the element at mid if it is greater than mid+1 or less than mid-1.
Step 6: Adjust the search range based on the sorted subarray.
Step 7: Return -1 if the loop completes without finding the minimum element.
Here is an implementation of finding the minimum number in a sorted rotated array using an optimized approach :
FileName:MinimumElementInRotatedSortedArray1.java
public class MinimumElementInRotatedSortedArray1 {
static int findMin(int[] arr, int n) {
if (n == 0)
return -1;
else if (n == 1)
return arr[0];
int start = 0, end = n - 1;
while (start <= end) {
// If the array is already sorted, return the first element
if (arr[start] <= arr[end])
return arr[start];
// Calculate the mid index
int mid = start + (end - start) / 2;
// Check if mid+1 is the minimum element
if (arr[mid] > arr[mid + 1])
return arr[mid + 1];
// Check if mid is the minimum element
if (arr[mid - 1] > arr[mid])
return arr[mid];
// Determine which half of the array to continue the search
if (arr[start] <= arr[mid])
start = mid + 1;
else
end = mid - 1;
}
return -1; // It should not be reached if the array is properly rotated
}
public static void main(String[] args) {
int[] arr = {4, 5, 1, 2, 3};
System.out.println("Minimum element in arr: " + findMin(arr, arr.length));
}
}
Output:
Minimum element in arr: 1
Complexity analysis: The time complexity for the above approach is O(log N). The algorithm finds the minimum element by binary search, which divides the search space in half for each iteration. The space complexity is O(1) because it only needs a fixed amount of additional space for variables, irrespective of the size of the input array.