蓝桥学院2019算法题2.17

 1 package recursion;
 2 
 3 /**
 4  * @author zsh
 5  * @company wlgzs
 6  * @create 2019-02-18 10:49
 7  * @Describe 题2·旋转数组的最小数字(改造二分法)
 8  * 把一个数组最开始的作干个元素搬到数组末尾，我们称之为数组的旋转。
 9  * 输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。
10  * 例如数组[3,4,5,1,2]为[1,2,3,4,5]的一个旋转，
11  * 该数组的最小值为1。
12  */
13 public class Main5 {
14 
15     /**
16      * 查找数组最小值
17      * @param arr 待查找的数组
18      * @return 最小值
19      */
20     static int min(int[] arr){
21         //头指针
22         int begin = 0;
23         //尾指针
24         int end = arr.length -1;
25         //考虑到没有旋转这种特殊的旋转
26         if (arr[begin] < arr[end])
27             return arr[begin];
28         //begin与end指向相邻元素，退出
29         while (begin +1 <end){
30             int middle = ((begin + end) >>> 1);
31             //注意特殊情况
32             //如果arr[begin] == arr[middle] == arr[end] ，采用扫描法
33             if (arr[begin] == arr[end] && arr[begin] == arr[middle] && arr[middle] == arr[end]){
34                 int min = 0;
35                 for (int i = 0; i ) {
36                     if (arr[i] < min){
37                         min = arr[i];
38                     }
39                 }
40                 return min;
41             }
42             //左边有序
43             if (arr[middle] >= arr[begin]){
44                 begin = middle;
45             }else {
46                 //右边有序
47                 end = middle;
48             }
49         }
50         return arr[end];
51     }
52 
53     public static void main(String[] args) {
54         int[] arr = new int[]{5,1,2,3,4};
55         System.out.println(min(arr));
56         arr = new int[]{2,3,4,5,6};
57         System.out.println(min(arr));
58         arr = new int[]{1,0,1,1,1};
59         System.out.println(min(arr));
60     }
61 }