刷题专栏（十八）：第一个错误的版本

前言

刷题专栏到目前已经是第十八篇了，欢迎大家来关注我的刷题专栏，一起来刷题。

今天的这道题《第一个错误的版本》中，主要是考察二分法的使用。

关于二分法，之前的文章中也有所介绍，大家如果有兴趣可以自行去看一下。

下面我们就一起来看一下吧。

算法题：第一个错误的版本

这道题的描述好长，读起来也并不好理解。

其实就是要在多个版本中，获取第一个错误的版本。

首先是错误的版本的概念，一旦出现错误时，就一直有错误版本。

所以在第一个错误版本出现后，后续的版本就都是错误的。

其实是可以把这个概念转换一下，替代成一个连续的整数数组，然后获取某个具体的整数值，也就更好理解了。

由此可见，我们是可以通过遍历来处理这个情况的。

但是遍历一般都会使用更多的性能，在这种情况下，使用更多的是二分法。

下面我们就来看一下代码是如何写的。

代码展示

代码通过二分法，来进行区间的缩小。

/* The isBadVersion API is defined in the parent class VersionControl.
      boolean isBadVersion(int version); */
public class Solution extends VersionControl {
    public int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) {
            int m = left + (right - left) / 2; 
            if (isBadVersion(m)) {
                right = m; 
            } else {
                left = m + 1; 
            }
        }
        return left;
    }
}

代码执行结果

运行11ms，竟然还能击败这么的大哥，着实没想到。

不过这内存消耗明显差了些。

总结

二分法的使用，通常用于获取某个区间内的一个数值，或者是集合中的某个元素。

通常会比直接遍历要快得多，所以在不确定区间数值中获取对应元素时，还是比较推荐二分法来处理。