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?Rust Solution
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);
}
Having problems with this solution? Click here to submit an issue on github.