33 & 81. Search in Rotated Sorted Array I & II

33. Search in Rotated Sorted Array

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

My Solutions:

方法1：在整个nums的范围里binary search。每一次根据反转的index在mid之前还是之后，以及target的位置，调整l和r的位置。

class Solution {
    public int search(int[] nums, int target) {

    if (nums == null || nums.length == 0) return -1;
    int l = 0, r = nums.length - 1;
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        
        if (nums[mid] < nums[r]) { // 反转的index在mid之前,mid之后的都是递增的
            // target在mid和r之间
            if (target > nums[mid] && target <= nums[r]) l = mid;
            else r = mid;

        } else { // 反转的index在mid之后,mid之前的都是递增的
            //target在mid和l之间
            if (target >= nums[l] && target < nums[mid]) r = mid;
            else l = mid;
        }
    }
    
    if (nums[l] == target) return l;
    else if (nums[r] == target) return r;
    else return -1;
}

方法2：先找到转折的index，检查target在转折之前还是之后，然后在那半段里binary search。

public int search(int[] nums, int target) {
    if (nums == null || nums.length == 0) return -1;

    int l = 0, r = nums.length - 1;

    // 先找到转折的index
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] > nums[r]) l = mid;
        else r = mid;
    }
    // this is the point of the largest element
    int changePoint = nums[l] > nums[r] ? l : r;

    // 找到target在转折index前还是后
    if (target >= nums[0] && target <= nums[changePoint]) {
        l = 0;
        r = changePoint;
    } else {
        l = changePoint;
        r = nums.length - 1;
    }

    // binary search
    while (l + 1 < r) {
        int mid = l + (r - l) / 2;
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) l = mid;
        else r = mid; 
    }
    if (nums[l] == target) return l;
    if (nums[r] == target) return r;
    return -1;
}

81. Search in Rotated Sorted Array II

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

Example 2:

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

Follow up:

• This is a follow-up problem to Search in Rotated Sorted Array, where nums may contain duplicates.

• Would this affect the run-time complexity? How and why?

My Solutions:

和33类似，因为有duplicate number的关系，需要把duplicate的去掉。

class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        if (nums.length == 1) return nums[0] == target;
        int l = 0, r = nums.length - 1;
        while (l + 1 < r) {
            int mid = l + (r - l ) / 2;
            if (nums[mid] == target) return true;
            // remove duplicates
            if (nums[l] == nums[mid] && nums[mid] == nums[r]) {
                l++;
                r--;
            }
            // 注意这里是连着上面的elseif，因为改变了l和r的值
            else if (nums[mid] <= nums[r]) { // 说明反转的index在mid之前，mid之后的都是递增的
                if (nums[mid] < target && target <= nums[r]) l = mid;
                else r = mid;
            } 
            else { // 说明反转的index在mid之后，mid之前的都是递增的
                if (nums[l] <= target && target < nums[mid]) r = mid;
                else l = mid;
            }
        }
        if (nums[l] == target) return true;
        if (nums[r] == target) return true;
        return false;
    }
}