ac

有序数组arr可能经过一次旋转处理，也可能没有，且arr可能存在重复的数。例如，有序数组[1, 2, 3, 4, 5, 6, 7]，可以旋转处理成[4, 5, 6,  7, 1, 2, 3]等。给定一个可能旋转过的有序数组arr，再给定一个数num，返回arr中是否含有num
关于旋转操作：可以简单的理解为把序列从某个位置切成两段然后交换位置

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 {
        String line = reader.readLine();
        String line2 = reader.readLine();
        String[] strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int k = Integer.valueOf(strArr[1]);
        strArr = line2.split(" ");
        int[] arr = new int[n];
        for(int i=0;i<n;i++){
            arr[i] = Integer.valueOf(strArr[i]);
        }
        System.out.println(findVal(arr, k) ? "Yes" : "No");
    }

    // 降序，生序
    static boolean findVal(int[] arr, int val){
        int pos = getMinIndexLeft(arr); // 找到最小的数的最左位置
        return bsearch(arr, pos, arr.length - 1, val) ||
                bsearch(arr, 0, pos - 1, val);
    }

    static int getMinIndexLeft(int[] a){
        int index =  getMinIndex(a, a.length);
        int pos = index-1;
        while (pos >= 0 && a[pos] == a[index]){
            pos--;
        }
        pos = pos + 1;
        return pos;
    }

    static boolean bsearch(int[] arr, int left, int right, int val){
        if(left > right){
            return false;
        }
        while (left <= right){
            int mid = (right - left) / 2 + left;
            if(arr[mid] == val){
                return true;
            }else if(arr[mid] < val){
                left = mid + 1;
            }else {
                right = mid - 1;
            }
        }
        return false;
    }

    static int getMinIndex(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 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 low;
                }else {
                    high = mid;
                    break;
                }
            }
        }
        return a[low] < a[high] ? low : high;
    }
}
/*
7 7
4 5 6 7 1 2 3

Yes

7 998244353
4 5 6 7 1 2 3

No
 */