33. Search in Rotated Sorted Array Medium

1/**
2 * [33] Search in Rotated Sorted Array
3 *
4 * There is an integer array nums sorted in ascending order (with distinct values).
5 * Prior to being passed to your function, nums is possibly rotated at an unknown pivot index k (1 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
6 * Given the array nums after the possible rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
7 * You must write an algorithm with O(log n) runtime complexity.
8 *  
9 * Example 1:
10 * Input: nums = [4,5,6,7,0,1,2], target = 0
11 * Output: 4
12 * Example 2:
13 * Input: nums = [4,5,6,7,0,1,2], target = 3
14 * Output: -1
15 * Example 3:
16 * Input: nums = [1], target = 0
17 * Output: -1
18 *  
19 * Constraints:
20 *
21 * 1 <= nums.length <= 5000
22 * -10^4 <= nums[i] <= 10^4
23 * All values of nums are unique.
24 * nums is an ascending array that is possibly rotated.
25 * -10^4 <= target <= 10^4
26 *
27 */
28pub struct Solution {}
29
30// problem: https://leetcode.com/problems/search-in-rotated-sorted-array/
31// discuss: https://leetcode.com/problems/search-in-rotated-sorted-array/discuss/?currentPage=1&orderBy=most_votes&query=
32
33// submission codes start here
34
35impl Solution {
36    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
37        let (mut start, mut end) = (0, nums.len() - 1);
38        while start <= end {
39            let mid = (end - start) / 2 + start;
40            println!("df {}", mid);
41            if nums[mid] == target {
42                return mid as i32;
43            } else if nums[mid] > target {
44                if nums[mid] >= nums[start] {
45                    if nums[start] > target {
46                        start = mid + 1;
47                    } else {
48                        if mid == 0 {
49                            break;
50                        }
51                        end = mid - 1;
52                    }
53                } else {
54                    if mid == 0 {
55                        break;
56                    }
57                    end = mid - 1;
58                }
59            } else {
60                if nums[mid] >= nums[start] {
61                    start = mid + 1;
62                } else {
63                    if nums[start] > target {
64                        start = mid + 1;
65                    } else {
66                        if mid == 0 {
67                            break;
68                        }
69                        end = mid - 1;
70                    }
71                }
72            }
73        }
74        -1
75    }
76}
77
78// submission codes end
79
80#[cfg(test)]
81mod tests {
82    use super::*;
83
84    #[test]
85    fn test_33() {
86        assert_eq!(Solution::search(vec![3, 1], 1), 1);
87        assert_eq!(Solution::search(vec![3, 1], 3), 0);
88        assert_eq!(Solution::search(vec![1, 3], 3), 1);
89        assert_eq!(Solution::search(vec![1, 3], 1), 0);
90        assert_eq!(Solution::search(vec![1, 3], 0), -1);
91        assert_eq!(Solution::search(vec![1, 3], 4), -1);
92        assert_eq!(Solution::search(vec![4], 1), -1);
93        assert_eq!(Solution::search(vec![4, 5, 6, 7, 0, 1, 2], 0), 4);
94        assert_eq!(Solution::search(vec![4, 5, 6, 7, 0, 1, 2], 6), 2);
95        assert_eq!(Solution::search(vec![4, 5, 6, 7, 0, 1, 2], 9), -1);
96        assert_eq!(Solution::search(vec![4, 5, 6, 7, 0, 1, 2], 2), 6);
97        assert_eq!(Solution::search(vec![4, 5, 6], 4), 0);
98    }
99}
100