## Description

Search in Rotated Sorted Array II

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., `[0,0,1,2,2,5,6]` might become `[2,5,6,0,0,1,2]`).

You are given a target value to search. If found in the array return `true`, otherwise return `false`.

Example 1:

``````Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
``````

Example 2:

``````Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
``````

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 `````` ``````class Solution { public: bool search(const std::vector& nums, int target) { int l = 0; int r = nums.size() - 1; int mid, lnum, mnum, rnum; while (l <= r) { mid = l + (r - l)/2; lnum = nums.at(l); mnum = nums.at(mid); rnum = nums.at(r); // 一次判断三个数 if (mnum == target || lnum == target || rnum == target) { return true; } else if (lnum < mnum) { // lnum < mnum 表示左边有序，那么判断target是否落在左边 if (target < mnum && target >= lnum) { r = mid - 1; } else { l = mid + 1; } } else if (rnum > mnum) { // rnum > mnum 表示右边有序，那么判断target是否落在右边 if (target > mnum && target <= rnum) { l = mid + 1; } else { r = mid - 1; } } else { // 收紧区域 r--, l++; } } return false; } }; ``````