Leetcode/F家,LinkedIn-69.sqrt(x) 和 367.valid perfect square(Binary Search)

69.Sqrt(x) - Binary Search

• Difficulty: Medium

https://leetcode.com/problems/sqrtx/
Implement int sqrt(int x).

Compute and return the square root of x.

sqrt(9)=3

Company： Bloomberg Apple Facebook
思路：用binary search找中间满足条件的数，满足条件的情况特别注意 ，总会在loop里return
            - always use x/mid to compare
            - return case: x/mid >= mid && x/(mid+1) < (mid+1)//eg: 5/2 >2; 5/3<3
Complexity: Time O(logN) Space O(1)

public class Solution {
    public int mySqrt(int x) {
        if(x==0){ return 0;}
        if(x==1){ return 1;}
        int start = 1,end = x;
        while(start<=end){
            int mid = start + (end-start)/2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1))// 特别注意满足条件，不止是等于
       return mid; 
      else if (x / mid < mid)//mid太大
       end = mid-1;
      else
       start = mid + 1;
        }
        return start;//什么都行。。。。
    }

}

延展题
367.Valid Perfect Square LinkedIn

• Difficulty: Medium

 https://leetcode.com/problems/valid-perfect-square/ 
1.做法1： 1+3+5+7+...
2.bitwise
3.double cast

public class Solution {
    public boolean isPerfectSquare(int num) {
        if(num==0||num==1){ return true;}
        int start = 1, end =num;
        while(start<=end){
            int mid = start+(end-start)/2;
            if(mid<=num/mid&&(mid+1)>num/(mid+1)){
                if((double)num/mid - mid==0.0 ){//和上题一样，加多一个判定条件
                    return true;
                }
                return false;
            }else if(mid>num/mid){
                end = mid - 1;
            }else{
                start = mid+1;
            }
        }
        return false;
    }
}