153.find-minimum-in-rotated-sorted-array.md

問題

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

回答

初回の回答:

1~n 回 rotate した配列の一番小さい要素を見つけるという問題なんだけど、これも二分探索を使って求める。自身と右隣の大小関係が逆転している部分を求めれば良くて、

• $ nums[m] > nums[m + 1] $ の場合、 $nums[m + 1]$ が一番小さい要素で終わり。
• 上記が false の場合、$nums[0] > nums[m]$ であればその間のどこかに求める要素があるはずなので左に絞る。そうでない場合、右に絞る。

という条件をコードに起こせば OK。それでも見つからなかった場合、一周回って rotate していない状態に戻っているということなので、単純に最初の要素を返せば OK。

impl Solution {
    pub fn find_min(nums: Vec<i32>) -> i32 {
        let mut l = 0;
        let mut r = nums.len() - 1;
        while l < r {
            let m = l + (r - l) / 2;
            if nums[m] > nums[m + 1] {
                return nums[m + 1];
            } else if nums[0] > nums[m] {
                r = m;
            } else {
                l = m + 1;
            }
        }
        nums[0]
    }
}