第一个错误的版本 First Bad Version

问题描述

这个问题是很简单的二分查找问题.

要查找顺序序列中的一个分界值, 分界值的左侧都是正常版本, 而右侧都是有问题的版本.

要注意二分的边界情况:

#![allow(unused)]
fn main() {
    // Binary Search
    pub fn first_bad_version1(&self, n: i32) -> i32 {
        debug_assert!(n >= 1);
        let mut left = 1;
        let mut right = n;

        while left <= right {
            let middle = left + (right - left) / 2;
            if self.isBadVersion(middle) {
                // [middle..right] 区间都是有问题的版本, 但是 middle - 1 则不确定是不是坏了的.
                right = middle;
            } else {
                // [left..middle] 区间都是没有问题的版本
                left = middle + 1;
            }
        }
        left
    }
}

时间复杂度是 O(log(n)), 空间复杂度是 O(1).