题目

题目来源：力扣（LeetCode）

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2

示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,
由于返回类型是整数，小数部分将被舍去。

思路分析

由于 x 平方根的整数部分 ans 是满足 k^2 ≤ x 的最大 k 值，因此我们可以对 k 进行二分查找，从而得到答案。
二分查找的下界为 0，上界可以粗略地设定为 x。在二分查找的每一步中，我们只需要比较中间元素 mid 的平方与 x 的大小关系，并通过比较的结果调整上下界的范围。

  1. /**
  2.  * @param {number} x
  3.  * @return {number}
  4.  */
  6. // 咱们将前面小于等于x的记为1，大于x的记为0；所以就把平方求解的问题抽象成，
  7. // 前面一堆1后面一堆0的二分查找，最后求最后一个1的位置 。
  8. var mySqrt = function (x) {
  9.     // 因为要找最后一个1的位置，假设head指向代表待查找的区间的第一个值，
  10.     // 求 y = 根号x;y最小是0，最大为x
  11.     let head = 0, tail = x, mid;
  12.     tail += 1;
  13.     for (let i = 0; i < 100; i++) {
  14.         // 避免计算超界
  15.         mid = head + ((tail - head) / 2.0);
  16.         if (mid * mid <= x) head = mid;
  17.         else tail = mid;
  18.     }
  19.     return Math.floor(head);
  20. };
  21.     // 骚操作的处理：
  22.     // 调整固定次数，为什么调整100次就能找到；
  23.     // 二分调整一次，就把带查找的区间的缩少一半
  24.     // 二分调整100次，待调整区间就是2的100次方分之一；
  25.     // 此时，head和tail就已经挨得很近很近了，所以head和tail之间的误差是可能仅有2的100次方分之一
  26.     // 可以认为两个是一个值，最后保留head的整数部分