278.第一个错误的版本

链接：278.第一个错误的版本
难度：Easy
标签：二分查找、交互
简介：实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

题解 1 - c

• 编辑时间：2021-11-28
• 内存消耗：5.5MB
• 编程语言：c
• 解法介绍：二分。

int firstBadVersion(int n) {
    long l = 1, r = 2147483647, m;
    while (l < r) {
        m = (r + l) / 2;
        // 每次中间值是错误版本，就右侧值左移当中间值
        if (isBadVersion(m)) r = m;
        // 否则就左侧点是成功版本，找中间值的后一个
        else l = m + 1;
    }
    return l;
}

题解 2 - typescript

• 编辑时间：2021-06-14
• 执行用时：84ms
• 内存消耗：39.2MB
• 编程语言：typescript
• 解法介绍：二分搜索。

function solution(isBadVersion: (version: number) => boolean): (n: number) => number {
  return (n: number): number => {
    const find = (start = 1, end = n): number => {
      if (start === end) return start;
      const mid = ~~((start + end) / 2);
      if (!isBadVersion(mid)) return find(mid + 1, end);
      else if (mid === 1 || !isBadVersion(mid - 1)) return mid;
      else return find(start, mid);
    };
    return find();
  };
}

题解 3 - cpp

• 编辑时间：2021-12-20
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：二分查找。

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