Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit993b820

Browse files
committed
02 (1) find first "..." in sorted array using binary search
1 parent91c7925 commit993b820

File tree

4 files changed

+176
-0
lines changed

4 files changed

+176
-0
lines changed
Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
###Find Bad Version (find first "..." element in sorted array)
2+
3+
To make life easier, we can consider the very easy situation, only one number exists.
4+
5+
```java
6+
/**
7+
********************************************************************
8+
* case I : left & right right left
9+
| | |
10+
index 0 ===> -1 0
11+
isBad true (null) true
12+
expect = 1 => return left + 1 (return the order not the index of bad version)
13+
********************************************************************
14+
* case II : left & right right left
15+
| | |
16+
index 0 ===> 0 1
17+
isBad false false (null)
18+
expect = 2 => return left + 1 (return the order not the index of bad version)
19+
********************************************************************
20+
* Summary: return left
21+
*/
22+
23+
```
Lines changed: 47 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,47 @@
1+
/**
2+
* Time : O(lgN) ; Space: O(1)
3+
* @tag : Binary Search; LintCode Copyright
4+
* @by : Steven Cooks
5+
* @date: Aug 23, 2015
6+
***************************************************************************
7+
* Description:
8+
*
9+
* he code base version is an integer start from 1 to n. One day, someone
10+
* committed a bad version in the code case, so it caused this version and
11+
* the following versions are all failed in the unit tests. Find the first
12+
* bad version.
13+
*
14+
* You can call isBadVersion to help you determine which version is the first
15+
* bad one. The details interface can be found in the code's annotation part.
16+
*
17+
***************************************************************************
18+
* {@link http://www.lintcode.com/en/problem/first-bad-version/ }
19+
*/
20+
package_02_FirstBadVersion;
21+
22+
publicclassSolution {
23+
24+
publicintfindFirstBadVersion(intn) {
25+
intleft =0;
26+
intright =n -1;
27+
while (left <=right) {
28+
intmid =left + (right -left) /2;
29+
booleanisBad =isBad(mid);
30+
if (!isBad) {
31+
left =mid +1;
32+
}else {
33+
right =mid -1;
34+
}
35+
}
36+
// return the order not the index of bad version
37+
// if require return -1 for situation no bad version exists
38+
// then return (left + 1) > n ? -1 : (left + 1);
39+
returnleft +1;
40+
}
41+
42+
// wrap the API call
43+
privatebooleanisBad (intv) {
44+
returnVersionControl.isBadVersion(v +1);
45+
}
46+
47+
}
Lines changed: 91 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,91 @@
1+
package_02_FirstBadVersion;
2+
3+
importstaticorg.junit.Assert.*;
4+
5+
importorg.junit.After;
6+
importorg.junit.Before;
7+
importorg.junit.Rule;
8+
importorg.junit.Test;
9+
importorg.junit.rules.Timeout;
10+
11+
publicclassSolutionTest {
12+
13+
/** Test method for {@link _02_FirstBadVersion.Solution } */
14+
Solutionsolution;
15+
16+
@Rule
17+
publicTimeoutglobalTimeout =newTimeout(200);
18+
19+
@Before
20+
publicvoidsetUp()throwsException {
21+
solution =newSolution();
22+
}
23+
24+
@After
25+
publicvoidtearDown()throwsException {
26+
solution =null;
27+
}
28+
29+
@Test
30+
publicvoidTest1() {
31+
intn =5;
32+
boolean[]controls =newboolean[n];
33+
intexpected =4;
34+
customControls(expected,controls);
35+
VersionControl.setControls(controls);
36+
intactual =solution.findFirstBadVersion(n);
37+
assertEquals(expected,actual);
38+
}
39+
40+
@Test
41+
publicvoidTest2() {
42+
intn =31;
43+
boolean[]controls =newboolean[n];
44+
intexpected =1;
45+
customControls(expected,controls);
46+
VersionControl.setControls(controls);
47+
intactual =solution.findFirstBadVersion(n);
48+
assertEquals(expected,actual);
49+
}
50+
51+
@Test
52+
publicvoidTest3() {
53+
intn =4;
54+
boolean[]controls =newboolean[n];
55+
intexpected =4;
56+
customControls(expected,controls);
57+
VersionControl.setControls(controls);
58+
intactual =solution.findFirstBadVersion(n);
59+
assertEquals(expected,actual);
60+
}
61+
62+
@Test
63+
publicvoidTest4() {
64+
intn =10;
65+
boolean[]controls =newboolean[n];
66+
intexpected =10;
67+
customControls(expected,controls);
68+
VersionControl.setControls(controls);
69+
intactual =solution.findFirstBadVersion(n);
70+
assertEquals(expected,actual);
71+
}
72+
73+
@Test
74+
publicvoidTest5() {
75+
intn =10;
76+
boolean[]controls =newboolean[n];
77+
intexpected =11;
78+
customControls(expected,controls);
79+
VersionControl.setControls(controls);
80+
intactual =solution.findFirstBadVersion(n);
81+
assertEquals(11,actual);
82+
}
83+
84+
privatevoidcustomControls(intexpected,boolean[]controls) {
85+
for (inti =expected -1;i <controls.length;i++) {
86+
controls[i] =true;
87+
}
88+
}
89+
90+
91+
}
Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package_02_FirstBadVersion;
2+
3+
publicclassVersionControl {
4+
5+
privatestaticboolean[]versions;
6+
7+
publicstaticbooleanisBadVersion(intv) {
8+
returnv >0 &&v <versions.length +1 &&versions[v -1];
9+
}
10+
11+
publicstaticvoidsetControls(boolean[]controls) {
12+
versions =controls;
13+
}
14+
15+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp