通知
此博客运行在jpress系统上,如果你喜欢此博客模板,请加QQ群:1061691290(whimurmur模板/jpress插件),免费下载使用

leetcode探索之二分查找学习 背景

821人浏览 / 0人评论 | 作者:whisper  | 分类: 设计模式与算法  | 标签: 设计模式与算法  /  leetcode  | 

作者:whisper

链接:http://proprogrammar.com:443/article/624

声明:请尊重原作者的劳动,如需转载请注明出处


    本章的目标是解释二分查找的工作原理,识别二分查找的不同方法,并简要介绍 3 种常用的二分查找模板。

    它是如何工作的?

    在最简单的形式中,二分查找对具有指定左索引和右索引的连续序列进行操作。这就是所谓的查找空间。二分查找维护查找空间的左、右和中间指示符,并比较查找目标或将查找条件应用于集合的中间值;如果条件不满足或值不相等,则清除目标不可能存在的那一半,并在剩下的一半上继续查找,直到成功为止。如果查以空的一半结束,则无法满足条件,并且无法找到目标。

    在接下来的章节中,我们将回顾如何识别二分查找问题,“为什么我们使用二分查找” 这一问题的原因,以及你以前可能不知道的 3 个不同的二分查找模板。由于二分查找是一个常见的面试主题,我们还将练习问题按不同的模板进行分类,以便你可以在实践使用到每一个。

    注意:

二进制搜索可以采用许多替代形式,并且可能并不总是直接搜索特定值。有时您希望应用特定条件或规则来确定接下来要搜索的哪一侧(左侧或右侧)。

    我们将在接下来的章节中提供一些例子。在这之前,你能自己写一个二分查找算法吗?

    算法-二分查找

 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target  ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。
    // 想法:使用二分查找
    public int search(int[] nums, int target) {
        int left = 0, right = nums.length - 1, mid;
        
        while(right >= left){
            mid = (right+left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else{
                left = mid + 1;
            }
        }
        
        return -1;
    }

    基本二分查找问题,左右端点向中间逼近找目标值,mid值是左右端点值和的一半,根据mid位置的值与target值的关系更新right或left,或者返回结果

    看其它的解法中mid的求法是这样的mid = left + (right - left) / 2; 加一次除一次不是挺好吗,为什么要减一次除一次加一次呢?

    识别和模板简介

    如何识别二分查找?

    如前所述,二分查找是一种在每次比较之后将查找空间一分为二的算法。每次需要查找集合中的索引或元素时,都应该考虑二分查找。如果集合是无序的,我们可以总是在应用二分查找之前先对其进行排序。

    成功的二分查找的 3 个部分

    二分查找一般由三个主要部分组成:

  1. 预处理 —— 如果集合未排序,则进行排序。

  2. 二分查找 —— 使用循环或递归在每次比较后将查找空间划分为两半。

  3. 后处理 —— 在剩余空间中确定可行的候选者。

    3 个二分查找模板

    当我们第一次学会二分查找时,我们可能会挣扎。我们可能会在网上研究数百个二分查找问题,每次我们查看开发人员的代码时,它的实现似乎都略有不同。尽管每个实现在每个步骤中都会将问题空间划分为原来的 1/2,但其中有许多问题:

  • 为什么执行方式略有不同?

  • 开发人员在想什么?

  • 哪种方法更容易?

  • 哪种方法更好?

    经过许多次失败的尝试并拉扯掉大量的头发后,我们找到了三个主要的二分查找模板。为了防止脱发,并使新的开发人员更容易学习和理解,我们在接下来的章节中提供了它们。


亲爱的读者:有时间可以点赞评论一下

点赞(0) 打赏

全部评论

还没有评论!