# Sword finger offer: 6. Minimum number of rotation array

## Minimum number of rotation array

Title:

To move the first elements of an array to the end of the array, we call it the rotation of the array Input a rotation of a non subtractive sort array, and output the minimum elements of the rotation array For example, array {3,4,5,1,2} is a rotation of {1,2,3,4,5} and the minimum value of the array is 1 NOTE: all the given elements are greater than 0. If the array size is 0, please return 0.

Idea 1:

Traverse the whole array to find the minimum number directly

```import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int[] array) {
if (array.length == 0) {
return 0;
}
int min = array[0];
int index = 0;
for (int i = 1; i < array.length; i++) {
if (min > array[i]) {
min = array[i];
index = i;
}
}

return array[index];
}
}
```

Idea two:

Opportunistic method: borrowing java's built-in sorting algorithm

```import java.util.ArrayList;
import java.util.*;
public class Solution {
public int minNumberInRotateArray(int[] array) {
Arrays.sort(array);
return array[0];
}
}
```

Idea three:

The method of binary search

```public static int minNumberInRotateArray(int[] array) {
if (array.length == 0) {
return 0;
}
int left = 0;
int right = array.length - 1;
int middle = left;

while (array[left] >= array[right]) {
// left points to the last number of the first increment subarray
// right points to the first number of the second subarray, which is the minimum number of the array
if (right - left == 1) {
middle = right;
break;
}

middle = (left + right) / 2;
// In special cases, if the three digits pointed to by left,middle,right are equal

// If the intermediate element is in the preceding increment sub array, it should be greater than or equal to the element pointed to by the first pointer.
// The smallest element in the array should follow the middle element. We can point the first pointer to the intermediate element,
// This reduces the scope of the search. The first pointer after the move is still in the preceding increment sub array.
if (array[middle] >= array[left]) {
left = middle;
}

// If the middle element is in the following increasing sub array, it should be less than or equal to the element pointed to by the second pointer.
// The smallest element in the array should be in front of the middle element.
if (array[middle] <= array[right]) {
right = middle;
}
}

return array[middle];
}
```

Keywords: Java less

Added by phpnow on Mon, 18 Nov 2019 16:33:29 +0200