基础二分法求解 first bad version，谢谢！

https://leetcode.com/problems/fi...lowing-3-solutions/


就是很基础的二分法，但是楼主一直有个点想不明白，上面的 link 贴了写了 3 种的 solution，第 3 个最简单，但是我要想清楚为什么return left要花一点时间，第1个solution我就比较好理解，第2个类似，就是更繁琐了，加了第二个判断条件。按道理这3个都是 log(n) 复杂度，求问大神他们区别到底在哪里呢？

三个解法都不好，不如在第三个解法的基础上用一个res variable来保存最后一次遇到的bad version, 然后遇到bad version一路往左检测，也就是=的时候继续往左，最后一次遇到的 bad version 就是first bad version.

第二个解法面试如果candidate坚持写，我应该会给low readability 的评价
code quality is not reach standard bar, candidate stuggle to keep the logic and code clean, code stil need a lot polishing.

红A 发表于 2023-7-11 17:02
三个解法都不好，不如在第三个解法的基础上用一个res variable来保存最后一次遇到的bad version, 然后遇到b ...

谢了，我改了下成这样了：

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 0, right = n - 1, middle;
        int result;
        while (left <= right) {
            middle = left + (right - left) / 2;
            if (isBadVersion(middle)) {
                right = middle - 1;
                result = middle;
            }
            else {
                left = middle + 1;
            }
        }
        return result;
    }
};

三者的区别主要在于可读性，前两个把特殊情况列出来了，来理清自己的代码思路，这很常见；

但第二个加的判断条件有点绕，而且他写的有点乱。

红A 发表于 2023-7-12 08:02
三个解法都不好，不如在第三个解法的基础上用一个res variable来保存最后一次遇到的bad version, 然后遇到b ...

这样复杂度不是会被提高吗？因为向左一个一个走其实会变成O(n)

我觉得第三个其实是最好理解的，因为left 和 right本质是区间的两边，有可能是左闭右闭有可能是左闭右开，所以无论右是什么，左即left一定是存在于区间内部的。当收敛到最终状态的时候，即最后一个，剩下的一定是left。

这样理解：After the loop, left is the minimal index satisfying the condition function

投第三个解法一票, 第三个解法算是二分法的标准解法了.

这个题里面left指向的是第一个isBadVersion为真的元素, right指向的是最后一个isBadVersion为假的元素. 在其他二分法的题目中也是类似的, left会指向第一个满足特定条件的元素, right会指向最后一个不满足那个条件的元素.

把C++里面std::lower_bound, std::upper_bound和std::equal_range弄明白就对二分法的边界结果会有很深刻的认识了

Javery 发表于 2023-7-12 02:40
这样复杂度不是会被提高吗？因为向左一个一个走其实会变成O(n)

我觉得第三个其实是最好理解的，因为le ...

第三个解法的基础上加的res，还是logn