专栏首页程序员开发者社区二分算法-LeetCode 69

二分算法-LeetCode 69

二分算法-LeetCode 69

二分算法

二分算法模板, 二分搜索即搜索一个数,如果存在,返回其索引,否则返回-1。

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; // 注意

    while(left <= right) { // 注意
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; // 注意
        else if (nums[mid] > target)
            right = mid - 1; // 注意
        }
    return -1;
}

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根,其中 x 是非负整数。

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

示例 1:

输入: 4

输出: 2

示例 2:

输入: 8

输出: 2

说明: 8 的平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

思路

一个数 x 的开方 sqrt 一定在 0 ~ x 之间,并且满足 sqrt == x / sqrt。可以利用二分查找在 0 ~ x 之间查找 sqrt。

代码实现:

public class LeetCode69 {
    // 二分算法
    int mySqrt(int x) {
        int l = 1;
        int h = x;
        while (l <= h) {
            int mid = l + (h - l) / 2;
            int sqrt = x / mid;
            if (sqrt == mid) {
                return mid;
            } else if (sqrt < mid) {
                h = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return h;
    }

    public static void main(String[] args) {
        System.out.println(new LeetCode69().mySqrt(8));
    }
}

本文分享自微信公众号 - 程序员开发者社区(gh_016ffe40d550),作者:猿星人

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-11-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 4 题解

    请你找出这两个正序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。

    王小明_HIT
  • 当数据量增加时,如何提升数据库性能?

    高并发下数据库的一种优化方案:读写分离。就是一老主从复制的技术使得数据库实现数据复制多份,增加抵抗大量并发的得写能力。提升数据库的查询性能。以提高数据的安全性,

    王小明_HIT
  • 谈谈反射机制,动态代理基于什么原理

    反射机制是Java语言提供的一种基础功能,赋予程序在运行时自省(introspect,官方用语)的能力。通过反射我们可以直接操作类或者对象,比如获取某个对象的类...

    王小明_HIT
  • LeetCode 1150. 检查一个数是否在数组中占绝大多数(二分查找)

    给出一个按 非递减 顺序排列的数组 nums,和一个目标数值 target。 假如数组 nums 中绝大多数元素的数值都等于 target,则返回 True,...

    Michael阿明
  • LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    Michael阿明
  • 剑指Offer - 面试题53 - I. 在排序数组中查找数字 I(二分查找的变形版本)

    类似题目:LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置(二分查找)

    Michael阿明
  • Leetcode 81 Search in Rotated Sorted Array II

    Follow up for "Search in Rotated Sorted Array": What if duplicates are allowed...

    triplebee
  • Codility MinMaxDivision

    有计时功能,还有自己编写测试样例功能,还有很多其他功能。给人营造一种完全融入到刷题状态的感觉。

    ShenduCC
  • HDU 3783 ZOJ

    ZOJ Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/...

    Angel_Kitty
  • 12寒假专辑:八、C语言其他考试重点

    1)字符串的 strlen() 和 strcat() 和strcmp() 和strcpy()的使用方法一定要记住。他们的参数都是地址。其中strcat() 和s...

    用户6755376

扫码关注云+社区

领取腾讯云代金券