题解 | #在旋转过的有序数组中寻找目标值#

一、思路——分情况讨论

• 情况1
  

• 情况2
  

• 情况3

• 发现，情况3可以被情况1和2所顺路讨论，代码见后边
  

二、坑点

比如：1,3寻找3
那么，nums[Right]可能和target相同，见代码中标记的易错点

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        // write code here

        int Len=nums.size();
        if( 0==Len ) return -1;
        if( 1==Len ) return (target==nums[0])? 0 : -1;

        //[Left,Right】
        //不能用[Left,Right)，原因是，左右2个点，我都需要使用
        int Left=0,Right=Len-1;

        //因为是[left,Right]，然后，我们考虑元素个数是『奇数和偶数』的临界
        //所以我们选择Left<Right
        //这样，当Left=Right的时候就算终止条件
        while( Left<Right )
        {
            int mid=( Right-Left )/2+Left;
            if( nums[mid]==target ) 
            {
                return mid;
            }


            //『易错点，比如1,3中找3，那么nums[left]就等于了nums[mid]
            if( nums[Left]<=nums[mid] )
            {
                //情况1，左边单调，右边是子问题
                //如果target落在左边就很好处理了，继续左边区间搜索
                ////『易错点』，nums[left]==target可能，比如
                if( nums[Left]<=target && target<nums[mid] )
                {
                    Right=mid-1;
                }
                else
                {
                    //否则只能去右边无序区间搜索了
                    Left=mid+1;
                }
            }//『易错点』
            else if( nums[mid]<=nums[Right] )
            {
                //情况2，右边单调，左边是子问题
                //如果target落在右边区间就很好了，去右边搜索
                ////『易错点』，nums[Right]==target可能，比如
                if( nums[mid]<target && target<=nums[Right])
                {
                    Left=mid+1;
                }
                else
                {
                    //否则只能去左边的无序区间搜索了
                    Right=mid-1;
                }
            }

        }

        return (nums[Left]==target)? Left : -1;

    }
};