class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = -1;
        int right = -1;
        int start1 = 0;
        int start2 = 0;
        for(int i = 0;i <= (m+n)/2;i++){
            left = right;
            if(start1 < m && (start2 >= n || nums1[start1] < nums2[start2])){
                right = nums1[start1++];
            }else{
                right = nums2[start2++];
            }
        }
        if((m+n) % 2 == 0)return ((double)left+right)/2;
        else return right;
        }
}

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int left = 0,right = n-1;
        //数组 [a1,a2...an,b1,b2...bn] 其中b1~bn小于a1
        while(left <= right){
            int mid = (left+right)/2;
            if(nums[mid] == target) return mid;
            if(nums[mid] >= nums[0]){ //说明mid在[a1,a2...an]区间
                if(target > nums[mid]){ //说明target在[mid,...an区间]
                    left = mid+1;
                }else if(target < nums[mid]){ //说明target在[a1,...mid]区间 或者在[b1,b2..bn]区间
                    if(target >= nums[0]){ //说明在[a1...mid]区间
                        right = mid -1;
                    }else{
                        left = mid + 1;
                    }
                }
            }else{ //说明mid在[b1,b2...bn]区间
                if(target < nums[mid]){// 说明target在[b1,b2...mid]
                    right = mid -1;
                }else{ //说明target在[mid...bn] 或者[a1...an]区间
                    if(target > nums[n-1]){ //说明target在[a1..an]区间
                        right = mid -1;
                    }else{ //说明在[mid...bn]区间
                        left = mid + 1;
                    }
                }
            }
        }
        return -1;
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        if(nums.length == 0) return new int[]{-1,-1};
        int left = lowBinarySearch(nums,target);
        int right = upBinarySearch(nums,target);
        return new int[]{left,right};
    }
    public int lowBinarySearch(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        while(left < right){
            int mid = left + right >> 1;
            if(nums[mid] >= target) right = mid;
            else left = mid + 1;
        }
        return nums[left]==target?left:-1;
    }
    public int upBinarySearch(int[] nums,int target){
        int left = 0;
        int right = nums.length-1;
        while(left < right){
            int mid = left + right +1>> 1;
            if(nums[mid] <= target) left = mid;
            else right = mid-1;
        }
        return nums[left]==target?left:-1;
    }
}