【Leetcode】69. Sqrt(x)（二分搜索）

妖狐艹你老母 2022-02-26 12:43 151阅读 0赞

Implement `int sqrt(int x)`.

Compute and return the square root of *x*, where *x* is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

**Example 1:**

Input: 4
    Output: 2

**Example 2:**

Input: 8
    Output: 2
    Explanation: The square root of 8 is 2.82842..., and since 
                 the decimal part is truncated, 2 is returned.

题目大意：

输出一个int范围内整数的平方根的整数部分。

解题思路：

通过二分查找出最佳位置。在判断时注意由于二分之后有些mid依然很大会超出int，所以我们可以用INPUT/mid来判断。

**此处代码mid的始终指向的是中间偏左的数。**

class Solution {
    public:
        int mySqrt(int x) {
            if(x==0) return 0;
            int l = 1, r = x; 
            while(true){
            	int mid = l + (r-l)/2;
            	if(mid > (x/mid)) r = mid-1;
            	else if(mid+1 > (x/(mid+1))) return mid;
            	else l = mid+1;
    		}
        }
    };

其实直接遍历1-46339也是可以过的。

class Solution {
    public:
        int mySqrt(int x) {
            // cout << 46339*46339 << endl;
            for(int i = 0; i<=46340 ;i++){
                if (i*i>=x) return i*i>x?i-1:i;
            }
            return 46340;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，151人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法|二分查找No.2】leetcode 69. x 的平方根

【算法|二分查找No.1】leetcode 69. x 的平方根

清疚/ 2024年04月27日 06:55/ 0 赞/ 97 阅读

相关 LeetCode_二分搜索_中等_74.搜索二维矩阵

目录 1.题目 2.思路 3.代码实现（Java） 1.题目编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特

àì夳堔傛蜴生んèń/ 2023年10月06日 19:04/ 0 赞/ 59 阅读

相关 LeetCode_二分搜索_简单_35.搜索插入位置

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于

逃离我推掉我的手/ 2023年10月06日 18:07/ 0 赞/ 20 阅读

相关 LeetCode_二分搜索_中等_33.搜索旋转排序数组

目录 1.题目 2.思路 3.代码实现（Java） 1.题目整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nu

╰半夏微凉°/ 2023年10月06日 18:07/ 0 赞/ 102 阅读

相关 leetcode 69.x的平方根（Java 二分查找 easy）

[https://leetcode-cn.com/problems/sqrtx/][https_leetcode-cn.com_problems_sqrtx] 实现int s

╰半夏微凉°/ 2023年08月17日 17:01/ 0 赞/ 124 阅读

相关排序和二分查找sqrtx-leetcode练习题

import java.io.BufferedReader; import java.io.IOException; import java.io.In

青旅半醒/ 2023年07月19日 05:48/ 0 赞/ 59 阅读

相关 LeetCode69. x 的平方根【二分查找】

题目难度：简单题目描述： > 实现 int sqrt(int x) 函数。 > > 计算并返回 x 的平方根，其中 x 是非负整数。 > > 由于返回类型是整数，结

Myth丶恋晨/ 2023年01月22日 10:51/ 0 赞/ 49 阅读

相关【Leetcode】69. Sqrt(x)（二分搜索）

Implement `int sqrt(int x)`. Compute and return the square root of x, where x is guaran

妖狐艹你老母/ 2022年02月26日 12:43/ 0 赞/ 152 阅读

相关 LeetCode 69

问题描述：实现 int sqrt(int x) 函数。计算并返回 x 的平方根，其中 x 是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

我就是我/ 2021年12月14日 03:27/ 0 赞/ 328 阅读

相关 leetcode 69题思考关于二分查找的模版

eetcode 69， Implement `int sqrt(int x)`. Compute and return the square root of *x*,...

系统管理员/ 2021年03月28日 12:38/ 0 赞/ 451 阅读