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

系统管理员 2021-03-28 12:38 413阅读 0赞

leetcode 69，

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.

注意看代码里面的注释

class Solution {
        public int mySqrt(int x) {
            if (x<=1) return x; 
            long left = 0;
            long right = x;
            while (left < right) {
                long mid = (left + right + 1)/2;
                if (mid * mid == x) { 
                    return (int)mid;
                } else if (mid * mid < x) {
        //关键就是当mid*mid < x的时候，mid可不可能成为结果，这道题里面答案显然是可能的， 但是对275来说就不是这样了， 因为必须是至少h个大于h的才行，所以应该用 mid = (left + right)/2   left = mid + 1;  right = mid;
                    left = mid;
                } else {
                    right = mid - 1;
                }
            }
            return (int)(left);
        }
    }

二分模版

1. 开始对于特殊情况， len <= 1的情况做特殊处理。

2. 模版一  mid = (left + right)/2;  left = mid + 1; right = mid;  leetcode 275题， 模版二  mid = (left + right + 1)/2;  left = mid; right = mid - 1;   应用于leetcode 69

3. 对于一定有解的情况直接返回即可， 如果可能没有结果的，最后一定要对left进行检验( 这个操作可能没用，但是不会有坏处 )

查找第一个满足条件的值的二分模板

````
mid = (left + right)/2;

if (target > nums[mid]) {

left = mid + 1;

} else {//<=情况

right = mid;

}

return left;
````

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

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

69. x 的平方根题目解题思路代码题目实现`int sqrt(int x)` 函数。计算并返回 x 的平方根，其中 x 是非负整

墨蓝/ 2023年10月05日 13:21/ 0 赞/ 40 阅读

相关【Leetcode每日一题】69. x 的平方根/Sqrt(x)|二分查找---day3

![在这里插入图片描述][b88c49c5b7e04dacaaed7cf2fc928687.gif_pic_center] > 博主简介：努力学习的预备程序媛一枚~ >

蔚落/ 2023年09月23日 22:53/ 0 赞/ 38 阅读

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

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

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

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

相关 leetcode——二分查找

leetcode——二分查找 1.x的平方根(69) 2.在排序数组中查找元素的第一个和最后一个位置 3.搜

忘是亡心i/ 2022年10月31日 13:39/ 0 赞/ 167 阅读

相关关于二分查找及其上下界问题的一些思考

个人认为在编程的时候，我的代码能力应该是到位的，但是昨天参加的某公司笔试彻底把这个想法给终结了，才意识到自己是多么的弱。其中印象最深刻的是一道关于二分查找上下界的问题。当时洋洋

妖狐艹你老母/ 2022年09月24日 10:30/ 0 赞/ 138 阅读

相关关于二分查找

摘至本人有道云笔记《关于二分查找》首先假设有个有序序列b b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1

爱被打了一巴掌/ 2022年05月09日 02:50/ 0 赞/ 158 阅读

相关【LeetCode】二分查找

Java code class Solution { public int search(int[] nums, int tar

╰半橙微兮°/ 2021年11月08日 23:52/ 0 赞/ 252 阅读

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

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

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