class Solution {
    public int search(int[] nums, int target) {
        int i = nums[0];
        if(i == target) return 0;
        boolean bool = target > i; //true为左边区域，false为右边区域
        int left = -1;
        int right = nums.length;
        int mid;
        while (left + 1 != right){
            mid = (left + right) / 2;
            if(nums[mid] == target){
                return mid;
            }
            //mid与target同区
            if(bool == nums[mid] >= i){
                if(nums[mid] < target ){
                    left = mid;
                }else {
                    right = mid;
                }
            //mid与target不同区
            }else { 
                if(nums[mid] >= i){ //mid在左区，让left往左
                    left = mid;
                }else {
                    right = mid; //mid在右区，让right往右
                }
            }
        }
        return -1;
    }
}

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1,-1};
        int a = Arrays.binarySearch(nums,target);
        if(a < 0){
            return res;
        }
        int len = nums.length;
        int left = a,right = a;
        while(left - 1 >= 0 && nums[left - 1] == nums[left]){
            left = Arrays.binarySearch(nums,0,left,target);
        }
        while(right + 1 <=  len - 1 && nums[right + 1] == nums[right]){
            right = Arrays.binarySearch(nums,right + 1,len,target);
        }
        res[0] = left;
        res[1] = right;
        return res;
    }
}

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        int mid;
        if(target < nums[left]){
            return 0;
        }
        if(target > nums[right]){
            return right + 1;
        }
        while(left <= right){
            mid = (left + right)/2;
            if(left + 1 == right || left == right ){
                if(nums[left] == target){
                    return left;
                }else{
                    return left + 1;
                }
            }
            if(target == nums[mid]){
                return mid;
            }else if(target < nums[mid]){
                right = mid;
            }else{
                left = mid;
            }
        }
        return 0;
    }
}

class Solution {
    public int mySqrt(int x) {
        return (int)Math.sqrt(x);
    }
}

class Solution {
    public int lengthOfLIS(int[] nums) {
		int res = Integer.MIN_VALUE;
		int[] dp = new int[nums.length];
		for (int i = 0; i < nums.length; i++) {
			dp[i] = 1;
			for (int j = 0; j < i; j++) {
				if(nums[i] > nums[j]) {
					dp[i] = Math.max(dp[j] + 1, dp[i]);
				}
			}
			res = Math.max(res, dp[i]);
		}
		return res;
    }
}

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        int len = nums.length;
        int left = 0, right = 0;
        int sum = 0;
        while (right < len) {
            sum += nums[right++];
            while (sum >= target) {
                res = Math.min(res, right - left);
                sum -= nums[left++];
            }
        }
        
        return (res == Integer.MAX_VALUE) ? 0 : res;
    }
}

class Solution {
    public int[] twoSum(int[] numbers, int target) {
		int[] res = new int[2];
		for(int i = 0;i < numbers.length;i++) {
			int temp;
			if((temp = Arrays.binarySearch(numbers, i + 1, numbers.length, target - numbers[i])) > 0) {
				res[0] = i + 1;
				res[1] = temp + 1;
				return res;		
			}
		}
		return null;
    }
}