[Leetcode] Sqrt(x)

Problem

Implement int sqrt(int x).

Compute and return the square root of x.

Analysis

• 二分搜索 [0,x]
• 若 mid*mid 等于x，或者 (mid*mid<x && (mid+1)*(mid+1)>x), 则返回mid
• 否则若mid*mid < x，则搜索 [mid+1, right]
• 否则若mid*mid > x, 则搜索 [left, mid-1]
• 注意 mid*mid 可能会溢出，要用long类型
• Time: O(log n)
• Space: O(1)

Code

Reference
[1] https://leetcode.com/problems/sqrtx/

	public class Solution {
	public int mySqrt(int x) {
	return (int)help(0,x,x);
	}
	public long help(long left, long right, int x){
	if(left==right) return left;
	long mid = left + (right-left)/2;
	if(mid*mid==x) return mid;
	//go left
	if(mid*mid>x)
	return help(left, mid-1, x);
	//
	else{
	//mid is the solution
	if( (mid+1)*(mid+1) > x ) return mid;
	//go right
	else return help(mid+1, right, x);
	}
	}
	}

view raw sqrt(x).java hosted with ❤ by GitHub