-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy path69-sqrt-x.js
More file actions
39 lines (33 loc) · 760 Bytes
/
69-sqrt-x.js
File metadata and controls
39 lines (33 loc) · 760 Bytes
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
/**
* Problem link: https://leetcode.com/problems/sqrtx/
* find sqrt (x)
* not allowed to use any built-in exponent function or operator
*
* Input: x = 4
* Output: 2
*
* Input: x = 8
* Output: 2 [decimal part is truncated, 2 is returned]
*
* Solution: Binary Search
*/
/**
* @param {number} x
* @return {number}
*/
var mySqrt = function(x) {
if (x == 1) {return x; }
let low = 0;
let high = Math.floor(x/2);
while (low < high) {
const mid = low + Math.floor((1+high-low)/2);
if (Math.floor((x/mid)/mid) < 1) {
high = mid - 1;
} else {
low = mid;
}
}
return low;
};
const res = mySqrt(131);
console.log("result: ", res);