FilesExpand file tree

master

/

sqrt.cpp

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

62 lines (52 loc) · 1.24 KB

master

/

sqrt.cpp

Copy path

Top

File metadata and controls

• Code
• Blame

62 lines (52 loc) · 1.24 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

// Source : https://oj.leetcode.com/problems/sqrtx/

// Author : Hao Chen

// Date : 2014-08-26

/**********************************************************************************

*

* Implement int sqrt(int x).

*

* Compute and return the square root of x.

*

**********************************************************************************/

#include <stdlib.h>

#include <iostream>

using namespace std;

int sqrt(int x) {

if (x <=0 ) return 0;

//the sqrt is not greater than x/2+1

int e = x/2+1;

int s = 0;

// binary search

while ( s <= e ) {

int mid = s + (e-s)/2;

long long sq = (long long)mid*(long long)mid;

if (sq == x ) return mid;

if (sq < x) {

s = mid + 1;

}else {

e = mid - 1;

}

}

return e;

}

// http://en.wikipedia.org/wiki/Newton%27s_method

int sqrt_nt(int x) {

if (x == 0) return 0;

double last = 0;

double res = 1;

while (res != last)

{

last = res;

res = (res + x / res) / 2;

}

return int(res);

}

int main(int argc, char**argv)

{

int n = 2;

if( argc > 1 ){

n = atoi(argv[1]);

}

cout << "sqrt(" << n << ") = " << sqrt(n) << endl;

return 0;

}