每日一练-第278题-第一个错误的版本

一、思路

二分查找——因为它可以快速地将版本范围缩小一半从而更快地找到第一个坏版本。

二、解题方法

维护一个左边界 left 和一个右边界 right在每一步循环中我们计算中间版本 mid然后检查它是否是坏版本。如果是坏版本说明第一个坏版本在 mid 或者它之前我们将 right 更新为 mid。如果不是坏版本说明第一个坏版本在 mid 之后我们将 left 更新为 mid + 1。最终当 left 和 right 相等时就找到了第一个坏版本。

三、code

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

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1;//设定一个左边界 left 和一个右边界 right
        int right=n;
        while(left<right)
        {
            int mid=left+(right-left)/2;
            if(isBadVersion(mid))
            {
                right=mid;
            }
            else
            {
                left=mid+1;
            }
        }
        return left;//也可以是right。当 left 和 right 相等时就找到了第一个坏版本。
        
    }
};

===================================================================== 

 ①

二分查找Binary Search是一种高效的搜索算法适用于已排序的数据集。它的核心思想是将待查找的数据与数据集的中间元素进行比较从而排除一半的数据然后继续在剩余的一半中继续查找以此类推直到找到目标元素或者确定目标元素不存在。

二分查找的步骤如下

1. 确定查找范围的起始点和终点通常是整个数据集的起始和终止位置。

2. 计算中间元素的位置。这可以通过 (start + end) / 2 来获得也可以使用 (start + end) >> 1 来获得这两种方法在整数运算中可以避免溢出问题。

3. 比较中间元素与目标元素的大小关系如果相等则找到了目标元素算法结束。

4. 如果中间元素比目标元素大那么目标元素应该在左半部分将终点位置更新为中间位置减一。

5. 如果中间元素比目标元素小那么目标元素应该在右半部分将起始位置更新为中间位置加一。

6. 重复步骤2到步骤5直到起始位置大于终点位置表示查找范围为空目标元素不存在。

二分查找是一种时间复杂度为 O(log n) 的算法因此在处理大规模数据时非常高效。然而它要求数据集是已排序的否则无法正确进行查找。

错误使用线性搜索来解决这个问题但是可能因为版本数量很多而导致超时。

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

class Solution {
public:
    int firstBadVersion(int n) {
        for (int i = 1; i <= n; ++i) {
            if (isBadVersion(i) == true) {
                return i;
            }
        }
        return -1; // 如果没有找到坏版本可以根据题目要求返回一个特定值
    }
};