RUST GYM v0.2.4

33. Search in Rotated Sorted Array

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

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

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

 

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1

Example 3:

Input: nums = [1], target = 0
Output: -1

 

Constraints:

  • 1 <= nums.length <= 5000
  • -104 <= nums[i] <= 104
  • All values of nums are unique.
  • nums is guaranteed to be rotated at some pivot.
  • -104 <= target <= 104

Rust Solution

struct Solution;

impl Solution {
    fn search(nums: Vec<i32>, target: i32) -> i32 {
        let n = nums.len();
        let mut l: i32 = 0;
        let mut r: i32 = n as i32 - 1;
        while l <= r {
            let m = (l + r) / 2;
            if target == nums[m as usize] {
                return m as i32;
            } else if nums[l as usize] <= nums[m as usize] {
                if nums[l as usize] <= target && target <= nums[m as usize] {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else {
                if nums[m as usize] <= target && target <= nums[r as usize] {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
        }
        -1
    }
}

#[test]
fn test() {
    let nums = vec![4, 5, 6, 7, 0, 1, 2];
    let target = 0;
    assert_eq!(Solution::search(nums, target), 4);
    let nums = vec![4, 5, 6, 7, 0, 1, 2];
    let target = 3;
    assert_eq!(Solution::search(nums, target), -1);
    let nums = vec![3, 5, 1];
    let target = 3;
    assert_eq!(Solution::search(nums, target), 0);
    let nums = vec![4, 5, 6, 7, 8, 1, 2, 3];
    let target = 8;
    assert_eq!(Solution::search(nums, target), 4);
}

Having problems with this solution? Click here to submit an issue on github.