Leetcode 33.搜索旋转排序数组【C++】

地址：https://leetcode-cn.com/problems/search-in-rotated-sorted-array/

题目

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。

搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。

你可以假设数组中不存在重复的元素。

你的算法时间复杂度必须是 O(log n) 级别。

示例 1:

输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4

示例 2:

输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1

解题思路

这个题如果是已排序的数组，那么用二分查找应该就是最快的，但是题目是进行了旋转后的数组。

其实仔细观察不难发现，相当于题目已经把一个已排序的数组分成了两部分，前面一部分的数较大，后面一部分的数较小。以示例中的数组 [4,5,6,7,0,1,2] 为例，前一部分的数为 [4,5,6,7] ，后一部分的数为 [0,1,2] ，前面一部分任意一个数都是大于后面一部分的数的。

与标准二分查找不同的是，这个题的二分的点并不是数组的正中心，并且我们也不知道具体是从哪里二分的（需要遍历查找）。但是可以肯定的是，题目给出的 target 只可能属于两部分中的一个部分，换言之 target 要么大于数组的第一个数，要么小于数组的最后一个数。

那么剩下的事情就好办了，只需要遍历找出 target 的位置即可，当然这里并不能用到二分查找，因为没法确定边界的位置，对于前面一部分来说没法确定右边界的位置，而对于后面一部分来说，没法确定左边界的位置，当然也可以通过遍历找到边界的位置的，但是显然既然都要遍历数组了，不就可以直接进行逐个比较了吗。

首先判断 target 可能在前面一部分还是在后面一部分，如果在前面一部分则从前往后遍历，如果在后面一部分则从后往前遍历，找到了就跳出循环，返回结果。如果找不到函数返回默认值 -1 。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int ans = -1;
        if (nums.empty()) return -1;
        if (target >= nums[0]) {
            //在前半部分找
            for (int i = 0; i < nums.size(); i++) {
                if (nums[i] == target) {
                    ans = i;
                    break;
                }
            }
        }
        else if (target <= nums.back()) {
            //在后半部分找
            for (int i = nums.size() - 1; i >= 0; i--) {
                if (nums[i] == target) {
                    ans = i;
                    break;
                }
            }
        }
        return ans;
    }
};