Commit7b96e63

applewjg

committed

Sqrt

Change-Id: I1fcca7720537bd8777b820629991c01ee03d4f98

1 parenta3b9763 commit7b96e63Copy full SHA for 7b96e63

File tree

+27

-0

lines changed

+27

-0

lines changed

Lines changed: 27 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,27 @@`
	`1`	`+/*`
	`2`	`+ Author: King, wangjingui@outlook.com`
	`3`	`+ Date: Apr 18, 2013`
	`4`	`+ Problem: Sqrt(x)`
	`5`	`+ Difficulty: Easy`
	`6`	`+ Source: http://leetcode.com/onlinejudge#question_69`
	`7`	`+ Notes:`
	`8`	`+ Implement int sqrt(int x).`
	`9`	`+ Compute and return the square root of x.`
	`10`	`+`
	`11`	`+ Solution: 1. Binary search in range [0, x / 2 + 1].`
	`12`	`+ 2. Newton iteration method. x(i+1) = (x(i) + n/x(i)) / 2.`
	`13`	`+ See my blog (http://www.cnblogs.com/AnnieKim/archive/2013/04/18/3028607.html) for more explanation (in Chinese).`
	`14`	`+ */`
	`15`	`+publicclassSolution {`
	`16`	`+publicintsqrt(intx) {`
	`17`	`+intleft =1,right =x/2;`
	`18`	`+if(x<2)returnx;`
	`19`	`+while (left <=right) {`
	`20`	`+intmid = (left +right)/2;`
	`21`	`+if (x/mid ==mid)returnmid;`
	`22`	`+if (x/mid >mid)left =mid +1;`
	`23`	`+elseright =mid -1;`
	`24`	`+ }`
	`25`	`+returnright;`
	`26`	`+ }`
	`27`	`+}`

Comments

(0)