Skip to content

Instantly share code, notes, and snippets.

@Jeffwan
Last active August 29, 2015 13:56
Show Gist options
  • Save Jeffwan/8851299 to your computer and use it in GitHub Desktop.
Save Jeffwan/8851299 to your computer and use it in GitHub Desktop.
Sqrt(x) @leetcode
package leetcode.binarySearch;
/**
* Solution: BinarySearch
*
* Tricky:
* 1. Misunderstand the question, input 5,output 2; input 2,output 1. If not found, return the closest but not -1;
* 2. I am not sure if 99 return 9 or 10, according to wrong answer, it seems like to be 9 even if 10 is closer.
* 3. Input:2147395599, Output:2147395598, Expected:46339 the problem here is overflow x=500000 25000*25000<1000000
* 4. we need to change mid * mid < target --> mid < target/mid if we use int !
* 5. We could use long instead of int because of operation complexity of int
* 6. to make it more efficient, the end should be x/2+1, squre(x/2+1) always >= square(x) !!!
*
* @author jeffwan
*
*/
public class Sqrt {
public int sqrt(int x) {
int start, end, mid;
start = 0;
end = x / 2 + 1;
while(start + 1 < end) {
mid = start + (end - start) / 2;
if (mid == x / mid) {
return mid;
} else if (mid < x / mid) {
start = mid;
} else {
end = mid;
}
}
if (start == x / start) {
return start;
}
if (end == x / end) {
return end;
}
return start;
}
// Use long to prevent overflow
public int sqrt2(int x) {
if (x < 0) {
return -1;
}
long start, end, mid;
start = 0;
end = x ;
while (start + 1 < end) {
mid = start + (end - start) / 2;
long square = mid * mid;
if ((long)x == square) {
return (int)mid;
} else if ((long)x < square ) {
end = mid;
} else {
start = mid;
}
}
if ((long)x == start * start) {
return (int)start;
}
return (int)start;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment