package com.company;
//leetcode:https://leetcode.com/problems/sqrtx/
public class Sqrt {
    public static void main(String[] args) {
        int ans = mySqrt(81);
        System.out.println(ans);
    }
    static int mySqrt(int x) {
        if (x == 0) return 0;
        int start = 1, end = x;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1))// Found the result
                return mid;
            else if (mid > x / mid)// Keep checking the left part
                end = mid;
            else {
                start = mid + 1;// Keep checking the right part
            }
        }
        return start;
    }
}