二分搜索法的探究与心得

时间:2024-02-11 22:55:29 标签:  心得  

引言

在计算机科学中,二分搜索(Binary Search)算法是一种在有序数组中查找特定元素的基本搜索技术。其优点在于高效的搜索速度,时间复杂度为 ( O(log n) ),这一点与时间复杂度为O(n) 的线性搜索法相比,效率提高了数个数量级。二分搜索的核心思想是“分而治之”,即将大问题分解为小问题来逐步解决。

二分搜索适用场景

二分搜索不仅适用于简单的有序数组查找,它也适用于任何可以通过单调性质进行决策的问题,如实数范围内的最优解搜索、概率问题中的阈值确定,以及在计算机图形学中的光线追踪技术等。掌握二分搜索不仅能提升算法效率,也有助于培养分析和解决问题的思维能力。

二分搜索的两种主流写法

传统上,二分搜索有两种流行的写法:左闭右闭 [left, right] 和左闭右开 [left, right)。左闭右闭写法的循环条件为 while (left <= right),而左闭右开写法的循环条件为 while (left < right)。这两种写法虽然在实现上略有不同,但都广泛应用于实践中。

左闭右闭写法

在这种写法中,搜索范围包括 leftright 指向的元素。每次循环将区间分为三部分:小于 mid 的元素、等于 mid 的元素和大于 mid 的元素。根据与 target 的比较结果,我们可以排除其中的一个区间。当 leftright 相遇时,循环结束,此时 leftright 指向相同的可能是 target 的位置。

左闭右开写法

而在左闭右开的写法中,right 指向的元素不包含在搜索范围内。这种方法的结束条件是 leftright 相邻,此时 left 指向的是最后一个不符合条件的元素,right 指向的是第一个符合条件的元素。

left + 1 != right 写法的探讨

这种写法本质上是左闭右开的一种变体。其优势在于处理边界的清晰性和减少了在循环中对 mid 的过度检查。

写法原理

这种写法的基本原理是保持 leftright 指针之间至少有一个元素的间隔。这样,left 永远指向不满足条件的最后一个元素,而 right 指向的是满足条件的第一个元素。当 leftright 相邻时,即 left + 1 == right,它们之间的元素就是我们要找的元素。

二分搜索写法的具体问题优势

left + 1 != right 方法在处理特定类型的问题时显示出其优势,如“查找第一个大于等于目标值的元素”或“查找最后一个小于等于目标值的元素”。在这些问题中,通过维护一个明确的未满足条件和已满足条件的界限,left + 1 != right 写法减少了对边界的额外检查,从而提高了代码的执行效率和可读性。

对边界的处理

使用 left + 1 != right 的方法,边界处理变得直观而简单。在传统的左闭右闭写法中,我们需要小心翼翼地处理 leftright 的更新条件,以避免出现无限循环或者错过目标元素。而在 left + 1 != right 的方法中,我们避免了这种直接更新 leftrightmid 的操作,因此减少了对边界处理的担忧。

对区间的考量

left + 1 != right 的二分搜索中,对区间的考量显得尤为重要。这种写法天然地支持左闭右开的区间操作,即 [left, right)。在每次循环中,我们将区间从 mid 处分割,并根据比较结果决定是将 left 移动到 mid,还是将 right 移动到 mid。由于我们总是保持 leftright 之间至少有一个元素的距离,因此可以确保 mid 永远不会与 leftright 重合,这减少了循环中可能的逻辑错误。

这种方法的一个显著优点是它使得二分搜索的每一步都更加明确。在传统的左闭右闭方法中,当我们找到 mid 满足条件时,我们可能需要额外的逻辑来确定是返回 mid,还是继续在左边或右边的区间中搜索。而在 left + 1 != right 方法中,这种情况得到了简化:我们总是在确信没有遗漏任何可能的元素时才结束循环。

细节解析

1)迭代的过程

 整个二分的过程是一个不断迭代区间的过程,并且 红色游标 指向的元素始终是 红色 的;绿色游标 指向的元素始终是 绿色 的。迭代的过程就是不断向 红绿边界 逼近的过程。

2)结束条件

迭代结束时,红色游标 和 绿色游标 刚好指向 红绿边界,且区间长度为 2。

3)游标初始值

为什么 红色游标 初始值为 −1,绿色游标 初始值为 n ?

  能否将 红色游标 初始化为 0,绿色游标 初始化为 n−1 ? 答案是否定的,试想一下,如果数据元素都是绿色,红色游标 初始化为 0 就违背了 " 红色游标 指向的元素始终是 红色 的 " 这个条件;反之,如果元素都是红色的,也有类似问题。

4)中点位置

5)死循环

上面的程序模板是否会进入死循环?

  我们可以这么来看,当区间为 2 时,循环结束。当区间为 3 时,它一定可以变成区间为 2 的情况,当区间为4时,一定可以变成区间为 2 或者 3 的情况,也就是任何一种情况下,区间一定会减小,并且当等于 2 时,循环结束。所以不会造成死循环。

实践中的应用

在实际应用中,left + 1 != right 的方法尤其适合于寻找区间的极值问题,例如寻找旋转排序数组中的最小元素,或者在一个由两种元素(如“红色”和“绿色”)组成的数组中找到颜色变化的边界。在这些情况下,这种二分搜索方法能够清晰地定位到边界点,而不需要额外的边界检查。

代码模板

public int binarySearch(int[] nums, int target) {int left = -1, right = nums.length; // 初始化left为-1,right为数组长度while (left + 1 != right) { // 当左右指针相邻时停止int mid = left + ((right - left) >> 1); // 计算中点if (check()) { left = mid; // 更新左(或右)指针} else { right = mid; // 更新左指针}}// 循环结束时,left 为指向第一个绿色元素(或者 right 为指向最后一个红色元素)return left;
}

边界情况讨论

在数组的开始和结束位置,left + 1 != right 方法通过简化的逻辑清晰地处理了边界情况。尤其是在数组的结束位置,这种写法自然而然地避免了数组越界的风险,这是因为它始终保持 right 指针在数组范围内。

优势总结

left + 1 != right 的二分搜索法在多个方面展现出它的优势:

  • 精确的边界控制:通过保持 leftright 之间的间隔,这种方法减少了边界值的特殊处理,使得代码更加简洁。
  • 逻辑一致性:更新 leftright 变得一致和直观,不再需要额外的 if 判断来避免包含或排除中点值。
  • 减少错误:由于不需要处理 mid - 1mid + 1,此方法减少了由于错误更新索引而导致的无限循环或漏掉正确元素的风险。
  • 清晰的搜索意图:代码清晰地表达了搜索意图,特别是在区间分割的策略上,这对于阅读和维护代码的人来说是一个巨大的优势。
  • 可扩展性:这种写法易于扩展到更复杂的场景,如多维数组的二分搜索,或者需要进行复杂判断逻辑的问题。

与传统二分的对比

与传统的二分搜索方法相比,left + 1 != right 的写法在概念上更为简单和直观,尤其是对于边界条件的处理。在传统的二分搜索中,如果不小心处理,很容易在边界条件上出现错误,比如忘记了 mid - 1mid + 1,或者在 while 循环的条件中使用了错误的比较运算符。而在 left + 1 != right 的方法中,这些问题都不复存在。我们可以用一种更加一致和安全的方式来处理搜索逻辑。

结论

left + 1 != right 的二分搜索方法以其简洁的边界处理和清晰的逻辑流程,提供了一种新颖而有效的解决问题的方法。它不仅加强了对二分搜索的理解,还扩展了这一算法的应用范围,使得开发者能够更容易地实现和维护相关的算法。

来源:分享自作者个人站点/博客

智能推荐

引言 在计算机科学中&#xff0c;二分搜索&#xff08;Binary Search&#xff09;算法是一种在有序数组中查找特定元素的基本搜索技术。其优点在于高效的搜索速度&#xff0c;时间复杂度为 ( O(log n) )&#xff0c;这一点与时间复杂度为O(n) 的线性搜索法相比&#xff0c;效率提高了数个数量级。二分搜索的核心思想是“分而治之”&#xff0c;即将大问题分解为小问题来逐步解决。 二分搜索适用场景 二分搜索不仅适用于简单的有序数组查找&#xff0c;它也适用于任何可以通过单调性质进行决策的问题&#xff0c;如实数范围内的最优解搜索、概率问题中的阈值确定&#xff0c;以及在计算机图形学中的光线追踪技

标签:心得  

本文介绍了几个常见的匹配算法,通过算法过程和算法分析介绍了各个算法的优缺点和使用场景,并为后续的搜索文章做个铺垫;读者可以通过比较几种算法的差异,进一步了解匹配算法演进过程以及解决问题的场景;KMP算法和Double-Array TireTree是其中算法思想的集大成者,希望读者重点关注。1 前言上文探究了数据结构和算法的一些基础和部分线性数据结构和部分简单非线性数据结构,本文我们来一起探究图论,以及一些字符串模式匹配的高级数据结构和算法。【搜索中常见数据结构与算法探究(一)】(https://developer.jdcloud.com/article/2153)搜索作为企业级系统的重要组成部分,越来越发挥着重要的

标签:数据结构  算法  常见  

1 前言ES现在已经被广泛的使用在日常的搜索中,Lucene作为它的内核值得我们深入研究,比如FST,下面就用两篇分享来介绍一些本文的主题:第一篇主要介绍数据结构和算法基础和分析方法,以及一些常用的典型的数据结构;第二篇主要介绍图论,以及自动机,KMP,FST等算法;下面开始第一篇2 引言“算法是计算机科学领域最重要的基石之一““编程语言虽然该学,但是学习计算机算法和理论更重要,因为计算机算法和理论更重要,因为计算机语言和开发平台日新月异,但万变不离其宗的是那些算法和理论,例如数据结构、算法、编译原理、计算机体

标签:数据结构  算法  常见  

作者:京东保险&nbsp;管顺利开篇最近使用Elasticsearch实现画像系统,实现的dmp的数据中台能力。同时调研了竞品的架构选型。以及重温了redis原理等。特此做一次es的总结和回顾。网上没看到有人用Elasticsearch来完成画像的。我来做第一次尝试。背景说完,我们先思考一件事,使用内存系统做数据库。他的优点是什么?他的痛点是什么?一、原理这里不在阐述全貌。只聊聊通讯、内存、持久化三部分。通讯es集群最小单元是三个节点。两个从节点搭配保证其高可用也是集群化的基础。那

标签:这款  引擎  Elasticsearch  

标签:

完整代码在最后 树结构&#xff1a; 1.树结构本身是一种天然的组织结构 2.高效 二

标签:java  

往期文章&#xff08;希望小伙伴们在看这篇文章之前&#xff0c;看一下往期文章&#xff09; &#xff08;1&#xff09;递归、搜索与回溯算法&#xff08;专题零&#xff1a;解释回溯算法中涉及到的名词&#xff09;【回溯算法入门必看】-CSDN博客 &#xff08;2&#xff09;递归、搜索与回溯算法&#xff08;专题一&#xff1a;递归&#xff09;-CSDN博客  深搜是实现递归的一种方式&#xff0c;接下来我们之间从题入手&#xff0c;深入浅出地了解深搜吧&#xff01;

标签:递归  

前言 二分图也是挺重要的,希望大家能够完全掌握&#xff01;&#xff01;&#xff01; 一、二分图的基础 二分图是这样一个图&#xff1a; 有两顶点集且图中每条边的的两个顶点分别位于两个顶点集中&#xff0c;每个顶点集中没有边直接相连接&#xff01; 无向图G为二分图的充分必要条件是&#xff0c;G至少有两个顶点,且其所有回路的长度均为偶数。 判断二分图的常见方法是染色法&#xff1a; 开始对任意一未染色的顶点染色&#xff0c;之后判断其相邻的顶点中&#xff0c;若未染色则将其染上和相邻顶点不同的颜色&#xff0c; 若

标签:第八期  

内容研究内容研究涉及对特定主题进行系统的调查,以收集可靠和相关的信息。这个过程对于技术作者来说至关重要,因为它有助于生成有价值的、准确的、信息丰富的和引人入胜的内容。它超越了基本的互联网搜索,包括阅读技术文档、采访专家、进行调查和分析数据。内容研究应以战略方式进行,考虑信息的用途、目标受众和要传达的关键信息。一个执行良好的内容研究过程可以帮助技术作者生成既清晰又简洁的高质量内容。主题得分主题得分是计算特定内容片段涵盖指定主题的程度的计算研究。通常在 0 到 100 的范围内进行测量,它使用不同的指标,例如关键字使用、语义相关性、主题覆盖深度等。主题得分越高,您的内容被认为更全面地涵盖目标主题

标签:得分  关键词  策略  内容  主题  

文章目录 前言1. 什么是 PCA &#xff1f;2. PCA 的原理2.1 协方差和方差2.2 核心思想2.3 步骤

标签:成分  

题目1&#xff1a;654 最大二叉树 题目链接&#xff1a;654 最大二叉树 题意 根据不重复的整数数组nums构建最大的二叉树 &#xff0c;根节点是数组中的最大值&#xff0c;最大值左边的子数组构建左子树&#xff0c;最大值右边的子数组构建右子树 nums数组中最少含有1个元素&#xff0c;并且nums中的元素数值均大于等于0 递归  递归三部曲&#xff1a;

标签:二叉树  

推荐阅读 智能化校园&#xff1a;深入探讨云端管理系统设计与实现&#xff08;一&#xff09; 智能化校园&#xff1a;深入探讨云端管理系统设计与实现&#xff08;二&#xff09; 文章目录

标签:

700 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点和一个值。 你需要在BST中找到节点值等于给定值的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则返回 NULL。 例如&#xff0c;

标签:二叉树  

文章目录 一、题目二、解法三、完整代码 所有的LeetCode题解索引&#xff0c;可以看这篇文章——【算法和数据结构】LeetCode题解。

标签:数据结构  

解题思路一&#xff1a; /**public class TreeNode {int val &#61; 0;TreeNode left &#61; null;TreeNode right &#61; null;public TreeNode(int val) {this.val &#61; val;}}*/// 一定要用自己的理解真正弄出来才行

标签:双向  

[本节目标] 1. 二叉搜索树实现 2.二叉树搜索树应用分析 3. 二叉树进阶面试题 1. 二叉搜索树 1.1 二叉搜索树概念 二叉搜索树又称二叉排序树&#xff0c;它或者是一棵空树&#xff0c;或者是具有以下性质的二叉树: 若它的左子树不为空&#xff0c;则左子树上所有节点的值都小于根节点的值若它的右子树不为空&#xff0c;则右子树上所有节点的值都

标签:

引言&#xff0c;少年们&#xff0c;大家好。在这里祝大家元旦快乐&#xff0c;我是博主那一脸阳光&#xff0c;今天来介绍二分查找 在计算机科学领域&#xff0c;搜

标签:算法  

搜索技巧(二)搜索条件详解上回我们已经学习了一些简单的搜索功能,比如设置搜索语句、分页方法、数量查询以及高亮和折叠的查询效果。而今天,我们将更加深入地学习其它搜索相关的内容。最核心的,就是布尔查询,也就是类似于我们在数据库中的 AND 和 OR 之类的语法。不过在这之前,就像是 Explain 可以分析数据库的查询语句一样。XS 也为我们提供了一个可以查看分词结果以及

标签:详解  条件  技巧  

思路 观察树的组成&#xff0c

标签:算法  

题目1&#xff1a;530 二叉搜索树的最小绝对差 题目链接&#xff1a;530 二叉搜索树的最小绝对差 题意 返回二叉搜索树的两个不同节点间的最小差值&#xff08;是一个正数&#xff0c;取绝对值&#xff09; 注意利用二叉搜索树的性质  中序遍历得到的是一个有序单调递增的数组 递归

标签:祖先  

引言打算写写树形数据结构:二叉查找树、红黑树、跳表和 B 树。这些数据结构都是为了解决同一个基本问题:如何快速地对一个大集合执行增删改查。本篇是第一篇,讲讲搜索树的基础:二叉搜索树。基本问题如何在一千万个手机号中快速找到 13012345432 这个号(以及相关联信息,如号主姓名)?最笨的方案把一千万个手机号从头到尾遍历一遍,直到找到该手机号,返回对应的姓名。其时间复杂度是 O(n)————当然这肯定不是我们要的方案。最秀的方案用散列表

标签:本质  

目录 1. 什么是记忆化搜索&#xff08;例子&#xff1a;斐波那契数&#xff09;

标签:递归  

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java

标签:数据结构  

猜你喜欢

一、题目 给你一个二叉树的根节点 root &#xff0c;判断其是否是一个有效的二叉搜索树。 有效 二叉搜索树定义如下&#xff1a; 节点的左子树只包含 小于 当前节点的数。节点的右子树只包含 大于 当前节点的数。所有左子树和右子树自身必须也是二叉搜索树。 示例 1&#xff1a;

标签:递归  

学习目标&#xff1a; 博主介绍: 27dCnc 专题 : 数据结构帮助小白快速入门 &#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d;&#x1f44d

标签:代码  

目录 二叉搜索树的最近公共祖先二叉搜索树中的插入操作删除二叉搜索树中的节点普通二叉树的删除方式 LeetCode 235. 二叉搜索树的最近公共祖先

标签:节点  

本篇文章的内容以各种tips为主,不间断更新&nbsp;2023/10/14 最近更新:使用?.快速判断Func<bool>类对象是否为空&nbsp;&nbsp;1.Unity Runtime Tips&nbsp;比较两个集合结构上是否相等

标签:心得  Unity3D  

题目1&#xff1a;235 二叉搜索树的最近公共祖先 题目链接&#xff1a;235 二叉搜索树的最近公共祖先 题意 找出二叉搜索树中两个指定节点的最近公共祖先 二叉搜索树中节点各不相同&#xff0c;且两个指定的节点均存在与二叉搜索树中&#xff0c;也不同 递归 递归三部曲&#xff1a; 1&#xff09;递归函数的参数和返回值

标签:节点  

广度优先搜索 广度优先搜索&#xff1a;从一个顶点出发&#xff08;由开始时顶点创造顺序优先决定&#xff09;&#xff0c;访问所有没有被访问过的临节点。然后在从被访问过的节点出发&#xff0c;重复之前的操作 如下为一个图 从1出发&#xff0c;先后访问2 3&#xff0c;之后2访问它的邻接点4&#xff0c;3访问它的邻接点5&#xff0

标签:数据结构  

目录 前言&#xff1a;  1.二叉搜索树 1.

标签:二叉树  

力扣2331.计算布尔二叉树值   深度搜索&#xff1a;是要进入最下面 二叉树直接往递归上去想&#xff08;易写&#xff0c;不易想&#xff09; public boolean evaluateTree(TreeNode root) {if(root.left&#61;&#61;null||root.right&#61;&#61;nul

标签:深度  

654.最大二叉树 1、题目链接&#xff1a;力扣&#xff08;LeetCode&#xff09;官网 - 全球极客挚爱的技术成长平台 2、文章讲解&#xff1a;代码随想录 3、题目&#xff1a; 给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下&#xff1a; 二叉树的根是数组中的最大元素。左子树是通过数组中最大值左边部分构造出的最大二叉树。

标签:二叉树  

1.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ChatGPT发展现状... 22.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ChatGPT如何与工业相结合... 23.&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ChatGPT在工业领域的研究与应用... 31.&nbsp;&n

标签:工况  认知  领域  工业  数据  

Problem: 240. 搜索二维矩阵 II

标签:矩阵  

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java

标签:数据结构  

搜索——进阶搜索算法DATE 20231031:补充一道好题 P4872 OIer们的东方梦(Dijkstra 分层图最短路)。前情提要~双向广搜、双向深搜堆优化的 Dijkstra一颗小小的 A-STAR不大聪明的 IDDFS(IDS)可爱的 IDA-STAR广搜、深搜这是进阶搜索算法,不说了直接上例题:以“P1514 引水问题”为例:点击查看代码

标签:进阶  算法  学习笔记  

哈喽,我是404,正在努力提升代码能力的未来女程序员(笑),这是我的第一篇博客,接下来会记录我的学习之路到我力扣完全可以手撕,废话不多说,正文开搞!  通过初见力扣经典题目704.二分查找和59.螺旋矩阵,我注意到区间的使用对于题解非常重要,开与闭的划定是解题的关键,以下是一些重要点:&nbsp;1.【】与【)的区别  首先贴上两幅图,借用一下代码随想录当中的图示:

标签:区间  重要性  

分布式搜索引擎ElasticSearch——搜索功能 文章目录 分布式搜索引擎ElasticSearch——搜索功能DSL查询文档DSL查询分类

标签:分布式  

本文主要介绍了 Docker 的另一个核心技术:Union File System。主要包括对 overlayfs 的演示,以及分析 docker 是如何借助 ufs 实现容器 rootfs 的。如果你对云原生技术充满好奇,想要深入了解更多相关的文章和资讯,欢迎关注微信公众号。搜索公众号【探索云原生】即可订阅1. 概述

标签:魔法  docker  OverlayFS  UnionFS  

本文主要介绍了 Docker 的另一个核心技术&#xff1a;Union File System。主要包括对 overlayfs 的演示&#xff0c;以及分析 docker 是如何借助 ufs 实现容器 rootfs 的。 如果你对云原生技术充满好奇

标签:魔法  

课程目标 了解树/图的深度遍历&#xff0c;宽度遍历基本原理&#xff1b;会使用python语言编写深度遍历&#xff0c;广度遍历代码&#xff1b;

标签:算法  

我参加了 奇想星球 与 Datawhale 举办的 【AI办公 X 财务】第一期&#xff0c;现在这是第二次打卡&#xff0c;也即自由探索&#xff0c;我选择 Modelscope 的 Agent 探索&#xff0c;并用gpts创作助理对比&#xff01; 最近想学学小红书的运营方法&#xff0c;选择了 小红书IP定位导师-挑战赛-Q*咖喱&#xff0c;现在来试试&#xff01;&#xff01;&#xff01;

标签:工具  

深度优先搜索&#xff0c;其核心思想就是以一个点作为搜索的起始点&#xff0c;沿着这个点的分支路径不断地深入&#xff0c;直到没有满足条件的点则退回&#xff0c;并以新的起始点为搜索的点&#xff0c;重复以上的过程&#xff0c;图的遍历就是以深度优先搜索思想为解决问题的核心思想。 而对于图的实现方式有两种&#xff0c;一种就是使用递归的方式&#xff0c;递归的过程可以将问题变得简单&#xff0c;但是同时带来了负面影响&#xff0c;就是当数据量较大的时候&#xff0c;会出现运行时间过长&#xff0c;耗时严重。而另一个实现的方式就是非递归的方式&#xff0c;如果在对解决问题的过程中有着高效率的需求的时候&#xff0c;就需要使用到非递归的方式&#x

标签:深度  

给你一个满足下述两条属性的 m x n 整数矩阵&#xff1a; 每行中的整数从左到右按非严格递增顺序排列。每行的第一个整数大于前一行的最后一个整数。 给你一个整数 target &#xff0c;如果 target 在矩阵中&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a;

标签:矩阵  

二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 235. 二叉搜索树的最近公共祖先 方法一&#xff

标签:节点  

二叉树part08 235.二叉搜索树的最近公共祖先 701.二叉搜索树中的插入操作 450.删除二叉搜索树中的节点 235. 二叉搜索树的最近公共祖先 方法一&#xff1a;递归法&#xff08;利用二叉搜索树性质&#xff09;

标签:节点  

题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。如下图所示image.png示例输入:{10,6,14,4,8,12,16}

标签:题解  双向  链表  LeetCode  

相关问题

相关文章

热门文章

推荐文章

相关标签