[leetcode] 278. First Bad Version

[leetcode] 278. First Bad Version

Description

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Given n = 5, and version = 4 is the first bad version.call isBadVersion(3) -> falsecall isBadVersion(5) -> truecall isBadVersion(4) -> trueThen 4 is the first bad version.

分析

题目的意思是：找出bad version版本的版本号。

其实是一个二分搜索问题，注意int mid=i+(j-i)/2能够避免数据溢出的问题。

代码

// Forward declaration of isBadVersion API.bool isBadVersion(int version);class Solution {public: int firstBadVersion(int n) { int i=1; int j=n; while(i

参考文献

​​[LeetCode] First Bad Version 第一个坏版本​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。