Search Minimum number in Rotated and Sorted Array in Java using Binary Search
Problem Description :
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
- [5, 6, 7, 0, 1, 2, 4] if it was rotated 3 times.
- [2, 4, 5, 6, 7, 0, 1] if it was rotated 5 times.
Example 1 :
Input :
[5, 6, 7, 0, 1, 2, 4]
Output :
0
Example 2 :
Input :
[5, 8, 10, 15, 20, 50, 100, 200]
Output :
5
Example 3 :
Input :
[100, 50, 25, 5, 1]
Output :
1
We will use Binary Search for finding solution.
Solution 1 : Find Minimum Element in Rotated Sorted Array in Java
import java.util.Scanner;
public class FindMinimumInRotatedSortedArray {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("Enter array size : ");
int size = sc.nextInt();
int[] array = new int[size];
// Taking user inputs
System.out.println("Enter array elements :");
for (int i = 0; i < array.length; i++) {
array[i] = sc.nextInt();
}
System.out.println("Output : "+findMinimum(array));
}
public static int findMinimum(int[] nums) {
int start = 0;
int end = nums.length-1;
// If array is not rotated
if (nums[start] <= nums[end]) {
return nums[0];
}
while (start <= end) {
int mid = (start+end)/2;
if (nums[mid] > nums[mid+1]) {
return nums[mid+1];
} else if (nums[mid] < nums[mid-1]) {
return nums[mid];
} else if (nums[start] <= nums[mid]) {
start = mid+1;
} else if (nums[mid] <= nums[end]) {
end = mid-1;
}
}
return -1;
}
}
Solution Explanation :
- Take two variables, start as 0 ad end as array length.
- In first condition check for array does not rotated. If it does not rotated just return 0th element of array no need to do anything else.
- Otherwise go through start <= end
- Take mid index.
- Here compare mid with mid+1 and mid-1 and return minimum element accordingly.
- Else skip left part if start <= mid or skip right part if mid <= end.
Other Similar Tutorials :
Comments
Post a Comment