【leetcode】278. 第一个错误的版本

题目内容

思路分析

本题是一道二分查找题目，掌握二分查找的写法后写起来比较简单。关于二分查找的写法可以见我写了首诗，让你闭着眼睛也能写对二分搜索，可以说讲的非常清楚。

方法一：找左侧边界的二分查找

基本上按模板来就行，和模板不同的是本题的查找只有是和不是两种状态，而非平时的大于/小于/等于；另外，本题的序号是从1开始的，而且不像平时的查找会出现left指针越界的情况。

代码

#include <vector>
#include <math.h>
#include <limits.h>

using namespace std;

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

bool isBadVersion(int version) {
   return version == 4 ? true : false;
}

// 找左侧边界的二分查找
// 时间复杂度O(logn)
// 空间复杂度O(1)
// https://labuladong.gitbook.io/algo/mu-lu-ye/er-fen-cha-zhao-xiang-jie
class Solution {
public:
    int firstBadVersion(int n) {
        int mid, left = 1, right = n; // 注意到版本号从1开始

        while (left <= right) {
           mid = left + (right - left) / 2; // 防止整数溢出
           if (isBadVersion(mid)) {
              right = mid - 1;
           } else {
              left = mid + 1; 
           }
        }
        
        // 闭区间本来要检查left是否溢出，但由于此题的特性，不检查
        
        return left;
    }
};

int main() {
   Solution s;
   int input{ 5 };
   int result = s.firstBadVersion(input);
   int a = 0;
}

收获

基本掌握了二分查找的写法