278.first-bad-version.md

問題

https://leetcode.com/problems/first-bad-version/

回答

初回の回答:

最初にバグを出したバージョンを二分探索で求める問題。isBadVersion(n: i32)が true ならそれはバグのあるバージョン、false なら正常なバージョンということになる。

探索するバージョンを m として

• isBadVersion(m) -> true: isBadVersion(m - 1) -> true: 範囲を左に絞ってもう一回
• isBadVersion(m) -> true: isBadVersion(m - 1) -> false: m が答え
• isBadVersion(m) -> false: isBadVersion(m + 1) -> true: m + 1 が答え
• isBadVersion(m) -> false: isBadVersion(m + 1) -> false: 範囲を右に絞ってもう一回

という条件を設定してコードに起こしてみた。

impl Solution {
    pub fn first_bad_version(&self, n: i32) -> i32 {
        let mut l = 1;
        let mut r = n;
        while l <= r {
            let m = l + (r - l) / 2;
            if self.isBadVersion(m) {
                if !self.isBadVersion(m - 1) {
                    return m;
                } else {
                    r = m;
                }
            } else {
                if self.isBadVersion(m + 1) {
                    return m + 1;
                } else {
                    l = m + 1;
                }
            }
        }
        1
    }
}

二回目の回答:

• isBadVersion(m) -> true: 範囲を左に絞ってもう一回
• isBadVersion(m) -> false: 範囲を右に絞ってもう一回

これをループで回していくだけで最初にバグを出したバージョンに自動的にたどり着くっぽかったので、もうちょい単純になった。

impl Solution {
    pub fn first_bad_version(&self, n: i32) -> i32 {
        let mut l = 1;
        let mut r = n;
        while l < r {
            let m = l + (r - l) / 2;
            if self.isBadVersion(m) {
                r = m;
            } else {
                l = m + 1;
            }
        }
        l
    }
}