Search in Rotated Sorted Array

Description

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.

Example
For [4, 5, 1, 2, 3] and target=1, return 2.
For [4, 5, 1, 2, 3] and target=0, return -1.

Challenge O(logN) time

Link

Lintcode_ladder

Method

1. Binary Search
2. x

Example

1. 1

class Solution {
    /** 
     * param A : an integer ratated sorted array
     * param target :  an integer to be searched
     * return : an integer
     */
public:
    int search(vector<int> &nums, int target) {
        // write your code here
        if (nums.empty()) {
            return -1;
        }
        int start = 0;
        int end = nums.size()-1;
        while (start+1 < end) {
            int mid = start + (end-start)/2;
            if (target == nums[mid]) {
                return mid;
            }
            // target in the right region, test mid<target<end or not
            if (nums[mid] <nums[start]) {
                if (target >= nums[mid] && target <= nums[end]) {
                    start = mid;
                } else {
                    end = mid;
                }
            } else {
            // target in the left region, test start<target<mid or not
                if (target <= nums[mid] && target >= nums[start]) {
                    end = mid;
                } else {
                    start = mid;
                }
            }
        }
        if (target == nums[start]) {
            return start;
        }
        if (target == nums[end]) {
            return end;
        }
        return -1;
    }
};

Similar problems

x

Tags

x