81. Search in Rotated Sorted Arr

题目链接

https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

解题思路

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

代码

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if (nums.empty()) {
            return false;
        }
        //先查找被反转的位置
        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);
        }
    }
    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]) {
            //相等，两边都要尝试
            int p = findPos(nums, m, r);
            if (p != -1) {
                return p;
            }
            return findPos(nums, l, m);
        }
        if (nums[m] > nums[l]) {
            return findPos(nums, m, r);
        } else {
            return findPos(nums, l, m);
        }

    }

    bool findVal(vector<int>& nums, int l, int r, int target) {
        if (l > r) {
            return false;
        }
        if (l == r) {
            return nums[l] == target;
        }
        int m = (l + r) / 2;
        if (nums[m] == target) {
            return true;
        } else if (nums[m] > target) {
            return findVal(nums, l, m - 1, target);
        } else {
            return findVal(nums, m + 1, r, target);
        }
    }

};