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

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

描述：给定一个整数数组nums，按升序排序，数组中的元素各不相同。

nums数组在传递给search函数之前，会在预先未知的某个下标t（0 <= t <= nums.length-1）上进行旋转，让数组变为[nums[t], nums[t+1], ..., nums[nums.length-1], nums[0], nums[1], ..., nums[t-1]]。

比如，数组[0,2,4,6,8,10]在下标3处旋转之后变为[6,8,10,0,2,4]

现在给定一个旋转后的数组nums和一个整数target，请你查找这个数组是不是存在这个target，如果存在，那么返回它的下标，如果不存在，返回-1

示例1：输入：[6,8,10,0,2,4],10，返回值：2

解法一：

思路分析：通读题目，发现给定了一个有序数组nums。该有序数组为升序排列，但是在下方中又明确告☞给定的是一个旋转后的数组，所以我们不需要考虑旋转的过程，直接查找这个数组是不是存在目标值，存在的话返回下标，不存在的话，返回-1即可。那么我们就通过这道题目温习一下查找数组中的目标值的代码。

实例分析：输入：[6,8,10,0,2,4],10，返回值：2，设置指针i，

具体C++代码为：

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();//判断循环条件
        for(int i = 0; i < len;i++){
            if(nums[i] == target)
                return i;
        }
        return -1;
    }
};

在该算法中，遍历了数组中的全部元素，故其时间复杂度为O(N)，空间复杂度为O(1)。

解法二：

思路分析：再次读题目，我们发现数组的旋转条件为根据旋转规则，使得数组变为[nums[t], nums[t+1], ..., nums[nums.length-1], nums[0], nums[1], ..., nums[t-1]]，根据分析，发现该有序数组被分为两段，两段内容两两有序，所以我们又可以通过二分法去解决该问题，就是不断的与中间值做比较。

当前半段有序时，即数组中间值比循环数组最左边的值大，则nums[left] < nums[mid]，当目标值比中间值小，比最左边的值大时，肯定在前面，否则就在后面，具体详见java程序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型一维数组 
     * @param target int整型 
     * @return int整型
     */
    public int search (int[] nums, int target) {
        // write code here
        int left = 0;//设置左指针为初始位置
        int right = nums.length - 1;//设置右指针为末尾位置
        while(left <= right){//循环条件
            int mid = left + (right - left) / 2;//中间值为
            if(nums[mid] == target){//判断中间值是否等于目标值
                return mid;
            }
            if(nums[mid] >= nums[left]){
                if(nums[mid] > target){
                    right = mid - 1;
                }
                else{
                    left = mid + 1;
                }
            }
            else{
                if(target > nums[mid] && target <= nums[right]){//目标值大于中间值且小于最右边的值
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
        }
        return -1;
    }
}

该算法中采用二分法进行判断，相当于折半查找，故时间复杂度为O(log₂N)，空间复杂度为O(1)。