33. Search in Rotated Sorted Arr

题目链接

https://leetcode.com/problems/next-permutation/

解题思路

1. 先找到数组被rotated的位置如果有的话。
2. 确定好位置之后再在排序的数据区间内查找元素。

代码

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.size() == 0) {
            return -1;
        }
        int pos = findPos(nums, 0, nums.size() - 1);
        if (pos == -1) {
            return findVal(nums, 0, nums.size() - 1, target);
        }
        if (target >= nums[0]) {
            return findVal(nums, 0, pos, target);
        } else {
            return findVal(nums, pos + 1, nums.size() - 1, target);
        }
    }

    //查找数组被rotated的位置，-1表示未被rotated
    int findPos(vector<int>& nums, int l, int r) {
        if (l == r) {
            return -1;
        }
        if (l + 1 == r) {
            if (nums[l] < nums[r]) {
                return -1;
            } else {
                return l;
            }
        }
        int m = (l + r) / 2;
        if (nums[m] > nums[l]) {
            return findPos(nums, m, r);
        } else {
            return findPos(nums, l, m);
        }

    }

    //在数据的指定区间内查找目标元素
    int findVal(vector<int>& nums, int l, int r, int target) {
        if (l > r) {
            return -1;
        }
        if (l == r) {
            if (nums[l] == target) {
                return l;
            } else {
                return -1;
            }
        }
        int m = (l + r) / 2;
        if (nums[m] == target) {
            return m;
        } else if (nums[m] > target) {
            return findVal(nums, l, m - 1, target);
        } else {
            return findVal(nums, m + 1, r, target);
        }
    }
};