Commit3a0c211

committed

Lintcode/src/chapter2_binary_search/FirstBadVersion.java

1 parent885b065 commit3a0c211Copy full SHA for 3a0c211

File tree

+48

-0

lines changed

+48

-0

lines changed

Lines changed: 48 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,48 @@`
	`1`	`+packagechapter2_binary_search;`
	`2`	`+`
	`3`	`+publicclassFirstBadVersion {`
	`4`	`+`
	`5`	`+privatestaticclassSVNRepo{`
	`6`	`+//this is a fake method to make this class happy in Eclipse.`
	`7`	`+publicstaticbooleanisBadVersion(intn){`
	`8`	`+returnfalse;`
	`9`	`+ }`
	`10`	`+ }`
	`11`	`+`
	`12`	`+/**`
	`13`	`+ * @param n: An integers.`
	`14`	`+ * @return: An integer which is the first bad version.`
	`15`	`+ */`
	`16`	`+publicintfindFirstBadVersion_solution1(intn) {`
	`17`	`+// write your code here`
	`18`	`+if (n ==1)returnn;`
	`19`	`+intleft =1,right =n;`
	`20`	`+while(left+1 <right){`
	`21`	`+intmid =left + (right-left)/2;`
	`22`	`+if(!SVNRepo.isBadVersion(mid))left =mid;`
	`23`	`+elseright =mid;`
	`24`	`+ }`
	`25`	`+if(SVNRepo.isBadVersion(left))returnleft;`
	`26`	`+returnright;`
	`27`	`+ }`
	`28`	`+`
	`29`	`+publicintfindFirstBadVersion_solution2(intn) {`
	`30`	`+// write your code here`
	`31`	`+intleft =1,right =n;`
	`32`	`+while(left+1 <right){`
	`33`	`+intmid =left + (right-left)/2;`
	`34`	`+if(!SVNRepo.isBadVersion(mid))left =mid;`
	`35`	`+elseright =mid;`
	`36`	`+ }`
	`37`	`+if(left !=right){`
	`38`	`+if(!SVNRepo.isBadVersion(left)){`
	`39`	`+if(SVNRepo.isBadVersion(right))returnright;`
	`40`	`+elsereturn -1;`
	`41`	`+ }elsereturnleft;`
	`42`	`+ }`
	`43`	`+if(SVNRepo.isBadVersion(left))returnleft;`
	`44`	`+return -1;`
	`45`	`+ }`
	`46`	`+`
	`47`	`+`
	`48`	`+}`

Comments

(0)