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

Analysis

Binary search variation.

因为有pivot，rotate过的sorted array无法直接用标准binary search，在判断和修改搜索区间时需要做一些改变。

先根据nums[mid] 与 nums[right] 的大小关系，先判断中点mid相对pivot的位置

然后根据target和nums[left], nums[right]的关系，有一段区间满足单调性，以此继续做binary search.

Solution

Binary Search - compare mid point determine search direction - O(logn) time - (10ms, 30.57%)

class Solution {
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > nums[right]) {
                if (target < nums[mid] && target >= nums[left]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            } else {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

Binary Search - Find the pivot position first

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

        //find the pivot
        int pivot = findPivot(nums, 0, nums.length - 1);
        int end = nums.length - 1;
        int pivotIndex = 0;

        for(int i = 0; i < nums.length; i++){
            if(nums[i] == pivot){
                pivotIndex = i;
            }
        }

        if(target == pivot){
            return pivotIndex;
        }
        else if(target >= pivot && target <= nums[end]){
            return binarySearch(nums, pivotIndex, end, target);
        }
        else {
            return binarySearch(nums, 0, pivotIndex, target);
        }
    }

    public int findPivot(int[] nums, int start, int end){
        if(start == end){
            return nums[start];
        }

        int mid = (start + end) / 2;

        if(nums[mid] > nums[mid + 1]){
            return nums[mid + 1];
        }
        else if(nums[start] < nums[mid]){
            return findPivot(nums, mid + 1, end);
        }
        else{
            return findPivot(nums, start, mid);
        }
    }

    public int binarySearch(int[] nums, int start, int end, int target){
        if(start == end){
            if(nums[start] == target){
                return start;
            }
            else{
                return -1;
            }
        }

        int mid = (start + end) / 2;

        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] < target){
            return binarySearch(nums, mid + 1, end, target);
        }
        else{
            return binarySearch(nums, start, mid, target);
        }

    }
}