|
1 | 1 | package com.fishercoder.solutions;
|
2 | 2 |
|
3 |
| -/** |
4 |
| - * 278. First Bad Version |
5 |
| - * |
6 |
| - * You are a product manager and currently leading a team to develop a new product. |
7 |
| - * Unfortunately, the latest version of your product fails the quality check. |
8 |
| - * Since each version is developed based on the previous version, all the versions after a bad version are also bad. |
9 |
| - * |
10 |
| - * Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, |
11 |
| - * which causes all the following ones to be bad. |
12 |
| - * |
13 |
| - * You are given an API bool isBadVersion(version) which will return whether version is bad. |
14 |
| - * Implement a function to find the first bad version. You should minimize the number of calls to the API. |
15 |
| - * |
16 |
| - * Example: |
17 |
| - * Given n = 5, and version = 4 is the first bad version. |
18 |
| - * call isBadVersion(3) -> false |
19 |
| - * call isBadVersion(5) -> true |
20 |
| - * call isBadVersion(4) -> true |
21 |
| - * Then 4 is the first bad version. |
22 |
| - * */ |
23 | 3 | public class _278 {
|
24 | 4 |
|
25 |
| - public static class Solution1 { |
26 |
| - public int firstBadVersion(int n) { |
27 |
| - int left = 1; |
28 |
| - int right = n; |
29 |
| - while (left < right) { |
30 |
| - int mid = left + (right - left) / 2; |
31 |
| - if (isBadVersion(mid)) { |
32 |
| - right = mid; |
33 |
| - } else { |
34 |
| - left = mid + 1; |
35 |
| - } |
36 |
| - } |
37 |
| - return left; |
38 |
| - } |
| 5 | + public static class Solution1 { |
| 6 | + public int firstBadVersion(int n) { |
| 7 | + int left = 1; |
| 8 | + int right = n; |
| 9 | + while (left < right) { |
| 10 | + int mid = left + (right - left) / 2; |
| 11 | + if (isBadVersion(mid)) { |
| 12 | + right = mid; |
| 13 | + } else { |
| 14 | + left = mid + 1; |
| 15 | + } |
| 16 | + } |
| 17 | + return left; |
| 18 | + } |
39 | 19 |
|
40 |
| - private boolean isBadVersion(int left) { |
41 |
| - //this is a fake method to make Eclipse happy |
42 |
| - return false; |
43 |
| - } |
44 |
| - } |
| 20 | + private boolean isBadVersion(int left) { |
| 21 | + //this is a fake method to make Eclipse happy |
| 22 | + return false; |
| 23 | + } |
| 24 | + } |
45 | 25 | }
|
0 commit comments