81. Search in Rotated Sorted Array II.md

81. Search in Rotated Sorted Array II

Question

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Thinking:

• Method:
  • 去取出中间的变量，如果等于起始位置，我们将最左侧的index + 1。
  • 如果大于最左边的变量，则说明左侧是升序。
  • 如果小于最左侧的变量，则说明右侧是升序。

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums.length == 0) return false;
        int mid = nums[nums.length / 2];
        return -1 != binarySearch(nums, 0, nums.length - 1, target);
    }
    private static int binarySearch(int[] nums, int low, int high, int target){
        if(low > high) return -1;
        int mid = (low + high) / 2;
        int lowVal = nums[low];
        int midVal = nums[mid];
        int highVal = nums[high];
        if(midVal == target) return mid;
        if(midVal == lowVal){
            return binarySearch(nums, low + 1, high, target);
        }else if(midVal > lowVal){  //left is sorted
            if(target < midVal && target >= lowVal)
                return binarySearch(nums, low, mid - 1, target);
            else
                return binarySearch(nums, mid + 1, high, target);
        }else{    //right is sorted
            if(target > midVal && target <= highVal)
                return binarySearch(nums, mid + 1, high, target);
            else
                return binarySearch(nums, low, mid - 1, target);
        }
    }
}

二刷

还是参考了一刷时候的结果，实际上要通过一个midVal == lowVal来去除左侧的重复项。

class Solution {
    public boolean search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return false;
        int len = nums.length;
        return -1 != binarySearch(nums, target, 0, len - 1);
    }
    private int binarySearch(int[] nums, int target, int low, int high){
        if(low > high) return -1;
        int mid = low + (high - low) / 2;
        int midVal = nums[mid], lowVal = nums[low], highVal = nums[high];
        if(midVal == target) return mid;
        if(midVal == lowVal)
            return binarySearch(nums, target, low + 1, high);
        else if(midVal > lowVal){ //left is sorted
            if(target < midVal && target >= lowVal)
                return binarySearch(nums, target, low, mid - 1);
            else
                return binarySearch(nums, target, mid + 1, high);
        }else{
            if(target > midVal && target <= highVal)
                return binarySearch(nums, target, mid + 1, high);
            else
                return binarySearch(nums, target, low, mid - 1);
        }
    }
}

Third Time

• Method 1: binary search, I get the answer by myself

   class Solution {
   	public boolean search(int[] nums, int target) {
   		if(nums == null || nums.length == 0) return false;
   		return search(nums, 0, nums.length - 1, target);
   	}
   	private boolean search(int[] nums, int low, int high, int target){
   		if(low > high) return false;
   		int mid = low + (high - low) / 2;
   		if(nums[mid] == target) return true;
   		while(low < mid && nums[low] == nums[mid]){low++;}
   		while(high > mid && nums[high] == nums[mid]){high--;}
   		if(nums[mid] >= nums[low]){    // left side is in order
   			if(target >= nums[low] && target < nums[mid]) return search(nums, low, mid - 1, target);
   			else return search(nums, mid + 1, high, target);
   		}else{ //right side is in order
   			if(target > nums[mid] && target <= nums[high]) return search(nums, mid + 1, high, target);
   			else return search(nums, low, mid - 1, target);
   		}
   	}
   }