Leetcode——69. x 的平方根

概述

69. x 的平方根

• 注意，返回的类型是整数，小数部分被舍去

分析

• 对于找x的平方根，我们很容易想到从[1, x)去尝试，即暴力求解

• 但是注意到[1,x)是一个有序数组，问题就变成了在一个有序数组寻找一个满足条件的值，那么容易想到二分法

• 因为返回的类型是整数，所以也会有找不到的情况，需要额外考虑

思路

二分思路？

略

当x的平方根为小数时，无法直接在整数数组中找到值，如何确定返回值呢？

• 首先，当我们二分找不到元素，失败时一定有L > R；

  这种情况下，可能是当L==R时，由于L移动引起的，也可能是由于R移动引起的，我们需要分一下L==R的情况：

  • 如果由L向后移动引起，则说明target > num[mid]，但舍去小数位要返回的值应该就是num[mid]，所以返回的值是R指向的元素
  • 如果有R向前移动引起，则说明target < num[mid]，舍去小数位要返回的值应该比num[mid]要小，所以返回的值是R指向的元素

代码

class Solution {
public:
    int mySqrt(int x) {
        if (x == 1) return 1;
        int L = 0, R = x / 2;	// 优化一下，只要考虑[0, x/2]的数组
        while (L <= R) {
            int mid = (R - L) / 2 + L;
            if (x == (long long)mid * mid )  return mid;	// 注意类型转换，防止int溢出
            else if ( x > (long long)mid * mid )  L = mid + 1;
            else    R = mid - 1;
        }
        return R;	// 返回R
    }
};