278. First Bad Version

问题:

给定到目前为止的最终版本号n

则已有[1,2,...,n]这些版本,

在这些版本中,若第一次出现了坏的版本,那么它之后的版本都为坏的版本。

求第一个坏版本的版本号。

给定API来判断某个版本x是否为坏的版本

bool isBadVersion(version)

Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false
call isBadVersion(5) -> true
call isBadVersion(4) -> true

Then 4 is the first bad version. 

  

解法:二分查找(Binary Search)

本问题,要查找,

第一个使得isBadVersion为true满足的,index

因此,我们可套用模版,g(x)->isBadVersion(x)

 

代码参考:

 1 class Solution {
 2 public:
 3     int firstBadVersion(int n) {
 4         int l = 1, r = n;
 5         while(l<r) {
 6             int m = l+(r-l)/2;
 7             if(isBadVersion(m)) {
 8                 r = m;
 9             } else {
10                 l = m+1;
11             }
12         }
13         return l;
14     }
15 };

 

上一篇:H5打造属于自己的视频播放器(HTML篇)


下一篇:Mysqldump报错问题