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

最直接的办法是直接循环，挨着比就完了

简单版（c++实现）

class Solution {
public:
    int search(vector<int>& nums, int target) {
        for (int i = 0; i < nums.size(); i ++) {
            if (nums[i] == target) // 找到直接返回
                return i;
        }
        return -1; // 未找到 返回-1
    }
};

简单易懂

优化版（c++版本）

class Solution {
public:
    // 找到旋转点 K
    int getK(vector<int> nums){
        for(int i=0; i<nums.size()-1; i++){
            if(nums[i+1] < nums[i]){
                return i+1;
            }
        }
        return 0;
    }
    
    int search(vector<int>& nums, int target) {
        // write code here
        int k = getK(nums);
        int start, end;
        if(k == 0){       //若K是0，则没旋转，从头到尾升序排列
            start=0; end=nums.size()-1;
        }else{            //K不是0的话，start和end指向最小值和最大值
            start=k; end=k-1;
        }
        if(target < nums[start] || target > nums[end]){
            return -1;    //比最小值小，或者比最大值大，直接返回-1
        }else{
            int i;
            if(k!=0){    //K不是0的话，要确定是从下标0开始比还是从下标K开始比
                if(target >= nums[0]){   //比下标0的数字大，就比前半段，即[0, k-1]
                    start=0; end=k-1;
                }else{
                    start=k; end=nums.size()-1;  //比下标0的数字小，就比后半段，即[k, end]
                }
            }
            //确定了比较区域，挨着比就行了
            for(i=start; i<=end; i++){
                if(nums[i] == target) return i;  //遇到一样的返回目标下标
            }
            return -1;  //如果到最后都没有，返回-1
        }
    }
};

思路比较简单，找到K，就可以判断比较区间。

找到了比较区间后，挨着比就可以了。