033 - Search in Rotated Sorted Array

Search in Rotated Sorted Array

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.

Hide Tags

Array Binary Search

Hide Similar Problems

(M) Search in Rotated Sorted Array II (M) Find Minimum in Rotated Sorted Array

 

再一次说明，在简单的题目上改变一点点，解答可能就麻烦不少。

因为数组rotate过了，所以二分查找的时候，

简单判断大于等于小于中间值就不够了，同样是大于中间值，两边都有可能。

那要判断分出来的一半是什么情况，在不在它的范围内，

因为加入了这个判断，所以还需要补一个，都不在左右范围内，返回-1。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int sz = nums.size();
        if(sz)
            return bsearch(nums, target, 0, sz-1);
        return 0;
    }
   
   
    int bsearch(vector<int>& nums, int tgt, int begin, int end)
    {
        if(begin>end)
            return -1;
           
        if(tgt == nums[begin])
            return begin;
        if(tgt == nums[end])
            return end;
           
        int mid = (begin+end)/2;
        if(tgt == nums[mid])
            return mid;
           
        if(((nums[begin]<nums[mid])&&((tgt>nums[begin])&&(tgt<nums[mid])))
            || ((nums[begin]>nums[mid])&&((tgt<nums[mid])||(tgt>nums[begin]))))
            return bsearch(nums, tgt, begin+1, mid-1);

        else if(((nums[mid]<nums[end])&&((tgt>nums[mid])&&(tgt<nums[end])))
            || ((nums[mid]>nums[end])&&((tgt>nums[mid])||(tgt<nums[end]))))
            return bsearch(nums, tgt, mid+1, end-1);
       
        else
            return -1;
    }
};

4 ms