编程导航算法村第九关 | 二分查找

这篇具有很好参考价值的文章主要介绍了编程导航算法村第九关 | 二分查找。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

编程导航算法村第九关 | 二分查找

  • LeetCode852.这个题的要求有点啰嗦,核心意思就是在数组中的某位位置i开始,从0到i是递增的,从i+1 到数组最后是递减的,让你找到这个最高点。
    详细要求是:符合下列属性的数组 arr 称为山脉数组 :arr.length >= 3存在 i(0 < i < arr.length - 1)使得:

    arr[0] < arr[1] < … arr[i-1] < arr[i]

    arr[i] > arr[i+1] > … > arr[arr.length - 1]
  • 思路:
    • 使用二分查找:
      • 首先确定左右边界
      • 因为必然不是第一个与最后一个,取值范围便是1,length-2
      • 分三种情况讨论
      • 左边递增区域
      • 右边递增区域
      • 找见最大值
public int peakIndexInMountainArray(int[] arr) {
        int left = 1;
        int right = arr.length - 2;

        while (left < right) {
            int mid = left + ((right - left) >> 1);
//            符合条件的情况

            if (arr[mid - 1] < arr[mid] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            if (arr[mid] > arr[mid - 1] && arr[mid] < arr[mid + 1]) {
                left = mid + 1;
            }
            if (arr[mid] < arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                right = mid - 1;
            }
        }
        return left;
    }

旋转数字的最小数字

LeetCode153 已知一个长度为 n 的数组,预先按照升序排列,经由1到n次旋转后,得到输入数组。例如原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到:

若旋转 4 次,则可以得到 [4,5,6,7,0,1,2]

若旋转 7 次,则可以得到 [0,1,2,4,5,6,7]

 public int findMin(int[] nums) {
//    如果最小值在中间
//    最小值在左边开端、右边开端

        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] < nums[right]) {
                right = mid;
            }
            else {
                left = mid + 1;
            }

        }

        return nums[left];
    }

找缺失数字

剑指offer题目: 一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。

  • 思路:
    • 找出第一个num[i]!=i的值就是返回值
public int missingNumber(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (nums[mid] == mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

优化求平方根

剑指offer题目
实现函数 int sqrt(int x).计算并返回x的平方根这个题的思路是用最快的方式找到n*n=x的n。这里涉及到四舍五入,所以采用折半进行比较:

  • 思路:在此处需要使用除法,如果使用乘法则可能会导致越界的问题
 public int mySqrt(int x) {
        int left = 1;
        int right = x;

        while (left <= right) {
            int mid = left + ((right - left) >> 1);

            if (x / mid > mid) {
                left = mid + 1;
            } else if (x / mid < mid) {
                right = mid - 1;
            } else if (x / mid == mid) {
                return mid;
            }
        }
        return right;

    }

二叉搜索树

2.1 二叉搜索树中搜索特定值
LeetCode 700.给定二叉搜索树(BST)的根节点和一个值。文章来源地址https://www.toymoban.com/news/detail-634759.html

  public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) {
            return null;
        }
        if (root.val == val) {
            return root;
        }
//        if (root.left != null && root.right != null) {
          return   searchBST(root.val > val ? root.left : root.right,val);
//        }
    }

验证二叉搜索树

  • LeetCode98.给你一个二叉树的根节点 root ,判断其是否是一个有效的二叉搜索树。
  • 需要按照中序遍历,判断左子树是否是二叉搜索树,记录当前节点的值,要保证后面节点的值要大于前面所有节点的值
 private long pre = Long.MIN_VALUE;

    public boolean isValidBST(TreeNode root) {
        if (root == null) {
            return true;
        }
        if (!isValidBST(root.left)) {
            return false;
        }
        if (root.left != null) {
            if (root.val <= root.left.val) {
                return false;
            }
        }
        if (root.right != null) {
            if (root.val >= root.right.val) {
                return false;
            }
        }
        if (root.val <= pre) {
            return false;
        }
        pre =  root.val;
        if (!isValidBST(root.right)) {
            return false;
        }
        return true;

    }

到了这里,关于编程导航算法村第九关 | 二分查找的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Python查找算法】二分查找、线性查找、哈希查找

    目录 1 二分查找算法  2 线性查找算法 3 哈希查找算法         二分查找(Binary Search)是一种用于在有序数据集合中查找特定元素的高效算法。它的工作原理基于将数据集合分成两半,然后逐步缩小搜索范围,直到找到目标元素或确定目标元素不存在。 以下是二分查找的

    2024年02月08日
    浏览(52)
  • Python数据结构与算法篇(五)-- 二分查找与二分答案

    1.1 定义         二分查找又称折半查找、二分搜索、折半搜索等,是一种在静态查找表中查找特定元素的算法。         所谓静态查找表,即只能对表内的元素做查找和读取操作,不允许插入或删除元素。         使用二分查找算法,必须保证查找表中存放的是有

    2023年04月20日
    浏览(48)
  • 【数据结构与算法】python实现二分查找

    二分查找 又称折半查找,它是一种效率较高的查找方法 原理:首先,假设表中元素是按升序排列,将表中间位置记录的与查找比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的大于查找,则

    2024年02月05日
    浏览(40)
  • 【算法】【Python3、动态规划、贪心、二分查找】力扣1671. 得到山形数组的最少删除次数

    1671. 得到山形数组的最少删除次数 给定一个整数数组 nums ,我们定义该数组为山形数组当且仅当: nums 的长度至少为 3。 存在一个下标 i 满足 0 i len(nums) - 1 且: nums[0] nums[1] ... nums[i - 1] nums[i] nums[i] nums[i + 1] ... nums[len(nums) - 1] 现在,给定整数数组 nums ,我们的目标是将其变为

    2024年01月18日
    浏览(54)
  • 【算法系列篇】二分查找——这还是你所知道的二分查找算法吗?

    在生活中,我们往往会遇到在数组中查找某个确定的元素的时候,通常我们会选择使用暴力解法,这样虽然简单,但是时间复杂度是O(N),时间效率比较低。那么是否有方法可以使得在具有二段性的数组中找某一特定的元素的时间复杂度低于0(N)呢?答案是肯定的,当我们可以

    2024年02月11日
    浏览(52)
  • 【算法系列 | 8】深入解析查找算法之—二分查找

    心若有阳光,你便会看见这个世界有那么多美好值得期待和向往。 决定开一个算法专栏,希望能帮助大家很好的了解算法。主要深入解析每个算法,从概念到示例。 我们一起努力,成为更好的自己! 今天第8讲,讲一下查找算法的二分查找 查找算法是很常见的一类问题,主

    2024年02月07日
    浏览(55)
  • C++二分算法(二分查找&二分答案)细节详解

     二分算法可以分为 二分查找 和 二分答案 。 以在一个 升序数组 中查找一个数为例。它每次考察数组当前部分的 中间元素 ,如果中间元素刚好是要找的,就结束搜索过程;如果中间元素小于所查找的值,那么左侧的只会更小,不会有所查找的元素,只需到右侧查找;如果

    2024年02月08日
    浏览(53)
  • 【算法】二分查找(整数二分和浮点数二分)

    大家好!今天我们来学习二分查找算法,这是一种效率很高的算法哦! 目录 1. 整数二分 2. 整数二分模板 3. 整数二分模板题 3.1 洛谷 P2249 【深基13.例1】查找 3.2 Acwing789. 数的范围 4. 浮点数二分 5. 浮点数二分模板 6. 浮点数二分模板题 6.1 Acwing 790.数的三次方根 6.2 洛谷 P1024 [

    2024年02月10日
    浏览(52)
  • 【算法】简单的二分查找算法

    一个简单的二分查找算法:         简单描述:算法由静态方法rank()实现,它接受一个整数键和一个有序的int数组作为参数,如果整数存在于数组,返回它的索引,否则返回-1,算法使用两个变量lo和hi,并保证整数如果存在于数组中则它一定存在于a[lo...hi]中,然后通过循

    2024年01月21日
    浏览(57)
  • 【算法小课堂】二分查找算法

    当我们要从一个序列中查找一个元素的时候,最快想到的方法就是顺序查找法(即:从前到后依次查找)。但这种方法过于无脑,就是暴力的把每个元素都排查一遍。元素个数少的时候还行,一旦元素个数多起来,效率是非常低下,所以在实际中这种查找的方法是被摒弃的。

    2024年02月08日
    浏览(39)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包