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);
        }
    }
}