.# 33. Search in Rotated Sorted Array

Hard (LinkedIn, Bloomberg, Uber, Facebook, Microsoft)

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.

Explaination

Time complexity is O(logn) To deal with duplicate, moving right-- or left++

public class Solution {

// test case:
// nums is equals to null or is empty
// nums contains only one element
// nums is sorted: [1,2,3,4,5]
// nums does not contain target
// nums will contain duplicate element

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

    int left = 0, right = nums.length - 1;

    while(left + 1 < right) {
        int mid = left + (right - left) / 2;

        if(nums[mid] == target) {
            return mid;
        }

        if(nums[mid] > nums[left] || nums[mid] > nums[right]) {
            if(target >= nums[left] && target < nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        } else if(nums[mid] < nums[left] || nums[mid] < nums[right]) {
            if(target > nums[mid] && target <= nums[right]) {
                left = mid;
            } else {
                right = mid;
            }
        }
    }

    if(nums[left] == target) {
        return left;
    } else if(nums[right] == target) {
        return right;
    } else {
        return -1;
    }
}

}

81. Search in Rotated Sorted Array II

Hard

Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed?

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

Write a function to determine if a given target is in the array.

Explaination

Time complexity is O(logn)

public class Solution {

public boolean search(int[] nums, int target) {
    if(nums == null || nums.length == 0) {
        return false;
    } else if(nums.length == 1) {
        return nums[0] == target ? true : false;
    }

    int left = 0, right = nums.length - 1;

    while(left + 1 < right) {
        int mid = left + (right - left) / 2;

        if(nums[mid] == target) {
            return true;
        }

        if(nums[mid] > nums[left] || nums[mid] > nums[right]) {
            if(target >= nums[left] && target < nums[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        } else if(nums[mid] < nums[left] || nums[mid] < nums[right]) {
            if(target > nums[mid] && target <= nums[right]) {
                left = mid;
            } else {
                right = mid;
            }
        } else {  // deal with the duplicate element
            right--;
        }
    }

    if(nums[left] == target || nums[right] == target) {
        return true;
    } else {
        return false;
    }
}

}