33. Search in Rotated Sorted Array

Question:

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

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

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

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

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

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

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Thinking:

• Method:
  1. 首先确定使用二分法，符合题目中要求的O(logn)。
  2. 即使经过rotate，至少有一半的数组是in order的，我们通过判断中间值是否大于开头就能确定前半段是不是in order。（即使前半段in order也不说明后半段不是in order）。
• 前半段in order:
  • target在low和mid之间，递归调用bs。
  • target不在head和mid之间，在mid + 1和high之间调用bs
• 前半段不是in order:
  • target在mid和high之间，调用bs。
  • target不在mid和high之间，在low， mid-1调用bs。
• 特殊情况：
  • 只有两个元素，low == mid，要特殊处理。

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

二刷

因为要Big-O为O（logN），所以我们要用二分法。 我们可以确定的是，至少有一半的数组是顺序的。

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