81. Search in Rotated Sorted Array II

You are given an integer array `nums` sorted in ascending order (not necessarily distinct values), and an integer `target`.

Suppose that `nums` is rotated at some pivot unknown to you beforehand (i.e., `[0,1,2,4,4,4,5,6,6,7]` might become `[4,5,6,6,7,0,1,2,4,4]`).

If `target` is found in the array return its index, otherwise, return `-1`.

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
```

Constraints:

• `1 <= nums.length <= 5000`
• `-104 <= nums[i] <= 104`
• `nums` is guaranteed to be rotated at some pivot.
• `-104 <= target <= 104`

Follow up: This problem is the same as Search in Rotated Sorted Array, where `nums` may contain duplicates. Would this affect the run-time complexity? How and why?

81. Search in Rotated Sorted Array II
``````struct Solution;
use std::cmp::Ordering::*;

impl Solution {
fn search(nums: Vec<i32>, target: i32) -> bool {
let n = nums.len();
if n == 0 {
return false;
}
let mut l = 0;
let mut r = n - 1;
while l < r {
let m = l + (r - l) / 2;
if nums[m] == target {
return true;
}
match nums[m].cmp(&nums[r]) {
Equal => {
r -= 1;
}
Less => {
if nums[m] < target && nums[r] >= target {
l = m + 1;
} else {
r = m;
}
}
Greater => {
if nums[m] > target && nums[l] <= target {
r = m;
} else {
l = m + 1;
}
}
}
}
nums[l] == target
}
}

#[test]
fn test() {
let nums = vec![2, 5, 6, 0, 0, 1, 2];
let target = 0;
let res = true;
assert_eq!(Solution::search(nums, target), res);
let nums = vec![2, 5, 6, 0, 0, 1, 2];
let target = 3;
let res = false;
assert_eq!(Solution::search(nums, target), res);
let nums = vec![1, 1];
let target = 0;
let res = false;
assert_eq!(Solution::search(nums, target), res);
let nums = vec![1, 3, 1, 1];
let target = 3;
let res = true;
assert_eq!(Solution::search(nums, target), res);
}
``````