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`

33. Search in Rotated Sorted Array
``````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);
}
``````