33.search-in-rotated-sorted-array.md

問題

https://leetcode.com/problems/search-in-rotated-sorted-array/

回答

初回の回答: rotate した配列を戻してから二分探索する

まずは rotate した境目を見つけるために、隣り合う要素の大小関係が逆転している部分を特定する。全体で $\mathcal{O}(\log{_2}{n})$ で計算しないといけないのに、この計算が $\mathcal{O}(n)$ になってしまっていた。n が巨大な数になったら計算量かなり増えてしまう。

rotate した配列を rotate_left で戻したあとは二分探索をして終わり。ただ変数の型が usize の場合は 0 未満にいけないので注意。right = middle - 1 と書くとマイナスになる場合があるのでバグってしまう。

impl Solution {
    pub fn search(nums: Vec<i32>, target: i32) -> i32 {
        let mut nums = nums;
        let length = nums.len();
        if length == 1 {
            if nums[0] == target {
                return 0;
            } else {
                return -1;
            }
        }

        let mut k = 0;
        while k + 1 < length {
            if nums[k] > nums[k + 1] {
                break;
            }
            k += 1;
        }
        nums.rotate_left(k + 1);

        let mut left = 0;
        let mut right = length;
        while left < right {
            let middle = (left + right) / 2;
            match nums[middle].cmp(&target) {
                std::cmp::Ordering::Equal => return ((middle + k + 1) % length) as i32,
                std::cmp::Ordering::Greater => right = middle,
                std::cmp::Ordering::Less => left = middle + 1,
            }
        }
        -1
    }
}

二回目の回答: rotate した部分の index を$\mathcal{O}(\log{_2}{n})$で取ってくる

初回の回答のうち、rotate した部分の index を特定する計算を $\mathcal{O}(n)$ -> $\mathcal{O}(\log{_2}{n})$ に改善したのみ。そのあとの二分探索は rotate を戻してから行った方が条件分岐も少なくなるので、in place で順番戻しちゃった方がいい気がする。

impl Solution {
    pub fn search_rotated2(nums: Vec<i32>, target: i32) -> i32 {
        let length = nums.len();
        if length == 1 {
            if nums[0] == target {
                return 0;
            } else {
                return -1;
            }
        }

        let mut left = 0;
        let mut right = length - 1;

        let mut k = 0;
        while left < right {
            let middle = (left + right) / 2;
            if middle == length - 1 {
                k = 0;
                break;
            }

            if nums.get(middle) > nums.get(middle + 1) {
                k = middle + 1;
                break;
            } else {
                if nums.get(left) < nums.get(middle) {
                    left = middle + 1;
                } else {
                    right = middle;
                }
            }
        }
        let mut nums = nums;
        nums.rotate_left(k);

        left = 0;
        right = length;
        while left < right {
            let middle = (left + right) / 2;
            match nums[middle].cmp(&target) {
                std::cmp::Ordering::Equal => return ((middle + k) % length) as i32,
                std::cmp::Ordering::Greater => right = middle,
                std::cmp::Ordering::Less => left = middle + 1,
            }
        }
        -1
    }
}