ac

有序数组arr可能经过一次旋转处理，也可能没有，且arr可能存在重复的数。例如，有序数组[1, 2, 3, 4, 5, 6, 7]，可以旋转处理成[4, 5, 6,  7, 1, 2, 3]等。给定一个可能旋转过的有序数组arr，返回arr中的最小值。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = sc.nextInt();
        }
        System.out.println(getMin(arr, n));
    }

    static int getMin(int[] a, int n){
        int low = 0;
        int high = n - 1;
        while (low < high){
            if(low == high -1){
                break;
            }
            // 没有旋转
            if(a[low] < a[high]){
                return a[low];
            }
            int mid = (low + high) / 2;
            // 类似 5 6 7 1 2 3 4; 5 > 1
            if(a[low] > a[mid]){
                // [low, mid]
                high = mid;
                continue;
            }
             // 类似 4 5 6 7 1 2 3; 7 > 3
            if(a[mid] > a[high]){
                // [mid, high]
                low = mid;
                continue;
            }
            // 其它特殊情况，可以直接O(n),也可以进一步判断再二分
            // a[low] <= a[mid] <= a[high]
            // 可能 1 1 1 2 2 2
            //    low  mid   high
            // 可能 1 1 2 2 2
            //    low  mid   high
            // 可能 2 2 2 1 1 2
            //    low  mid   high
            // 可能 2 1 1 2 2 2 2
            //    low  mid   high
            while (low < mid){
                if(a[low] == a[mid]){
                    low++;
                }else if(a[low] < a[mid]){
                    return a[low];
                }else {
                    high = mid;
                    break;
                }
            }

        }
        return Math.min(a[low], a[high]);
    }
}
/*
7
4 5 6 7 1 2 3

7
6 7 1 2 3 4 5

7
5 6 7 1 2 3 4

7
2 1 1 2 2 2 2
 */