33/81. Search in Rotated Sorted ArrayI/II

Suppose a sorted array 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.
复杂度: time O(logn) space O(1)
思路: 因为rotate的缘故,当我们切取一半的时候可能会出现mid在左半边区间,或者右半边区间的情况,所以我们要做进一步的判断。假设数组是A,起始start,终止end,还有中间位置是mid。在每次迭代中,分三种情况:

A[mid] = target 找到target
A[mid] > A[start] 说明mid在左半边区间(4 5 6 7)有序的, 那么就要判断target是否在start与mid之间, 如果在的话则把m设为end边界, 否则的话target就在另外的一半, 把mid设为start边界
如果A[mid] < A[start], 说明mid在右半边区间(0 1 2 ), 那么就判断target是不是在mid到end之间.如果target在的话把mid设为start, 否则把mid设为end
最后再判断A[start],A[end]与target的关系.

public class Solution {
    public int search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return -1;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] > nums[start]) { // 4 5 6 7
                if (nums[mid] >= target && target >= nums[start]) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else { // 0 1 2
                if (nums[mid] <= target && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            }
        }
        if (nums[start] == target) {
            return start;
        } else if (nums[end] == target) {
            return end;
        }
        return -1;
    }
}

包含duplicate的:
复杂度: time O(n), space O(1),
思路: 由于存在duplicate情况,我们还是用mid跟end进行比较,当存在在num[mid]==num[end]时候,我们无法进行二分,只能逐步减小end的范围,此时end–; 同理start也是存在此情况,则start++;

public class Solution {
    public boolean search(int[] nums, int target) {
        if (nums == null || nums.length == 0) return false;
        int start = 0;
        int end = nums.length - 1;
        while(start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (nums[mid] == target) {
                return true;
            } else if (nums[mid] > nums[start]) { // 4 5 6 7
                if (target >= nums[start] && nums[mid] >= target) {
                    end = mid;
                } else {
                    start = mid;
                }
            } else if (nums[mid] < nums[start]) { // 0 1 2
                if (target <= nums[end] && nums[mid] <= target) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
                start++;
            }
        }
        if (nums[start] == target || nums[end] == target) 
            return true;
        return false;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s