LeetCode 278 First Bad Version

标签: 二分搜索 LeetCode 发布于:2022-02-02 23:36:19 编辑于:2022-02-05 16:55:27 浏览量:396

题目分析

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

迭代法

最后一次循环时,r 和 l 相同,且此时其为坏版本,左边是非坏版本,因此之后 r = m - 1,因此 l 即最后一个坏版本。

注意题目说了必然有坏版本,因此就不需要检查 l 是不是坏版本了。

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int l = 1;
        int r = n;
        while (l <= r) {
            int m = l + (r - l) / 2;
            if (isBadVersion(m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return l;
    }
};

未经允许,禁止转载,本文源站链接:https://iamazing.cn/