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.