题目分析

题目的数据量是1e7，暴力法可以直接通过，小伙伴们能否想到更优的方法？

二分查找

题目的意图是让我们使用二分查找来解决这个题目，题意中明确说了这是一个升序排列后的数组，经过了旋转，因此打乱了原先的排列顺序。这个题目和Leetcode33题和Leetcode81题非常类似，小伙伴们可以做完这个题目之后做一些另外两道。

旋转后可能出现三种情况，我们分别对其讨论，如下图所示。

因此最坏的情况下算法的**时间复杂度仍是$O(n)$，正常情况下算法的时间复杂度为$O(log(n))$，空间复杂度为$O(1)$**。

#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int search(vector<int>& arr, int target) {
        int left = 0, right = arr.size() - 1;
        while (left < right) {
            int mid = (left + right) >> 1;
            if (arr[mid] > arr[left]) {
                if (target >= arr[left] && target <= arr[mid]) right = mid;
                else left = mid + 1;
            }
            else if (arr[mid] < arr[left]){
                if (target >= arr[left] || target <= arr[mid]) right = mid;
                else left = mid + 1;
            }
            else {
                if (arr[left] == target) right = left;
                else left++;
            }
        }
        return arr[left] == target ? left : -1;
    }
};

刷题总结

这类题目是二分查找的扩展题型，二分查找是算法的重点内容，也是面试笔试的常考知识点，希望小伙伴们能深刻理解。