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

妖狐艹你老母 2022-02-26 12:43 122阅读 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 条评论，122人围观）

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

相关阅读

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

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

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

相关 LeetCode_二分搜索_中等_162. 寻找峰值

目录 1.题目 2.思路 3.代码实现（Java） 1.题目峰值元素是指其值严格大于左右相邻值的元素。给你一个整数数组 nums，找到峰值

﹏ヽ暗。殇╰゛Y/ 2023年10月06日 22:53/ 0 赞/ 4 阅读

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

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

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

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

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

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

相关 LeetCode 35. 搜索插入位置（二分查找）

上一篇博客：[LeetCode 28. 实现 strStr()（KMP、字符串）][LeetCode 28. _ strStr_KMP] > 写在前面：大家好！我是`ACf

客官°小女子只卖身不卖艺/ 2022年11月29日 13:09/ 0 赞/ 130 阅读

相关 LeetCode 搜索旋转排序数组【二分查找】

1 二分查找整数数组 nums 按升序排列，数组中的值互不相同。在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）

短命女/ 2022年09月12日 06:54/ 0 赞/ 153 阅读

相关 LeetCode 搜索二维矩阵【二分查找】

1 搜索二维矩阵编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：每行中的整数从左到右按升序排列。每行的第一个整数大于前一

ゞ浴缸里的玫瑰/ 2022年09月09日 11:56/ 0 赞/ 155 阅读

相关【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 赞/ 123 阅读

相关 LeetCode 69

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

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

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

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

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