解法一：暴力

  • (修正)之前的分析有些错误的地方，没有考虑数组旋转的带来的影响(具体已经在解法二中修正了)。大意的理解为就是给你一个数组和target（目标值）,让寻找与目标值相同的元素并返回对应索引，如果不存在就返回-1；比较典型的二分题目。其实题目中对数组的旋转还是有些坑！！！
  • 此类问题，首先想到的是暴力搜，可以AC!。
  • 这个很暴力，应该没什么问题。

    C++参考代码：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @param target int整型 
     * @return int整型
     */
    int search(vector<int>& nums, int target) {
        //获取数组长度
        int len = nums.size();
        for(int i=0;i<len;i++){
            if(nums[i]==target){
                return i;
            }
        }
        //不存在target，返回-1
        return -1;
    }
};

复杂度分析：

时间复杂度：O(N) ，其中N为数组长度，最坏情况下遍历整个数组。

空间复杂度：O(1) 没有开辟额外空间，因此空间复杂度为常数开销。

解法二：二分查找

  • 涉及到查找问题，一般情况下，二分查找都是一个可以 考虑的选择。
  • 相比于暴力，二分的速度会快很多，简单的二分实现起来也并不很难。
  • 由于数组可能在某个位置开始进行了旋转，因此不能直接套用常规的二分，得与中间值比较，分前半段