Question (in Chinese): http://ac.jobdu.com/problem.php?pid=1386
Question Name: Min Number In Rotated Array
Question Description: the input array is sorted and then rotated. Write a function to find the minimum value in the array.
Input: may contains multiple test cases. For each case, the first line is an integer N, saying the number of elements in the array. The second line contains N integers as the content of the array.
Output: the minimum value in each test case.
1 2 3 4 5 | Input: 5 3 4 5 1 2 Output: 1 |
This question is quite similar with the challenge Search in Rotated Sorted Array from LeetCode.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 | /** * Filename : MinNumberInRotatedArray.java * Dependency: None * Author : Sheng Yu (codesays.com) * Create at : 2014-08-01 * JDK used : 1.7 * Change log: None */ import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.StreamTokenizer; public class MinNumberInRotatedArray { /** * Stub for testing. * @param args: command line arguments * @throws IOException */ public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader( new InputStreamReader(System.in))); MinNumberInRotatedArray finder = new MinNumberInRotatedArray(); int size = 0; int[] input = null; int minValue = -1; while (st.nextToken() == StreamTokenizer.TT_NUMBER) { // Begin a new test case by getting the number of items. size = (int) st.nval; input = new int[size]; // Read the array, which is sorted and the rotated. for (int i = 0; i < size; ++i) { st.nextToken(); input[i] = (int) st.nval; } // Find the minimum element in the array. minValue = finder.minInRotatedArray(input, 0, size); System.out.println(minValue); } } /** * The the minimum element in the rotatedArray from begin to end position. * @param rotatedArray : the sorted-then-rotated array to search. * @param begin : the begin (inclusive) position of the array to search. * @param end : the end (exclusive) position of the array to search. * @return an integer : the minimum value in the array. */ public int minInRotatedArray(int[] rotatedArray, int begin, int end) { // Only one element in the range [begin, end), it is the minimum in the range. if (begin == end -1) return rotatedArray[begin]; // It is totally sorted in the range [begin, end), the first element is the minimum. if (rotatedArray[begin] < rotatedArray[end-1]) return rotatedArray[begin]; int mid = (begin + end) / 2; // The middle point. int min = rotatedArray[mid]; if (begin < mid) { // If the array has some element before middle point, find the minimum value // in that part, and compare it with the current min value. int temp = minInRotatedArray(rotatedArray, begin, mid); if (temp < min) min = temp; } if (mid + 1 < end) { // If the array has some element after middle point, find the minimum value // in that part, and compare it with the current min value. int temp = minInRotatedArray(rotatedArray, mid+1, end); if (temp < min) min = temp; } return min; } } |