ToB企服应用市场:ToB评测及商务社交产业平台

标题: 二分查找的区间到底是开还是闭？ [打印本页]

作者: 忿忿的泥巴坨 时间: 2024-11-27 10:17
标题: 二分查找的区间到底是开还是闭？
二分查找的区间到底是开还是闭？

在这两个月的时间里，我似乎没有产出任何的有关知识点的文章，大多数都是题解相关的内容。以至于许多人觉得 Macw07 “失踪”了。本文是我来到北美之后的第一篇知识点文章，请大家多多关照。

这次不讲难的知识点了，讲一个大家都熟悉的，但又非常令人抓毛的算法：二分查找和二分答案算法。
弁言 Introduction

留意：本文仅针对了解过二分查找基本算法原理的用户群体，若您从未接触过或了解过该算法，请先学习底子的二分查找算法。
二分查找算法是大家一个再熟悉不过的算法了，二分查找算法可以在一个 有序数列 中高效地查找某个或多个特定的目的值。一般来说，二分查找的时间复杂度在 \(O(\log_2 N))\) 级别。二分算法非常适合在大数据集上实现快速查询。与此同时，除了基本的二分查找算法，它的许多变种也被广泛应用于各种场景，比如求最大值、最小值，乃至在复杂的数据结构中优化数据的查找性能。
许多同学肯定在学习完基本的二分查找后一直有一个疑问：我到底该如何设置 \(L\) 和 \(R\) 的区间闭合状态？什么时候必要输出 \(L\) 或 \(R\)，为什么偶然候还必要 \(+1\)？\(\text{Mid}\) 到底保存的是什么东西？etc.
事实上，区间开闭的变量定义 确实是一个核心且容易混淆的题目，在 CSP 考试中也常考此知识点，因此本文将重点围绕区间开闭的变量定义来展开。
二分查找的基本原理 Basic Principles of Binary Search

在深入讨论区间开闭之前，有必要回顾一下二分查找的基本原理。二分查找通过反复将搜索区间分成两半，逐步缩小目的值所在的范围，直到找到目的值或确定其不存在。具体步骤如下：

初始化：设定搜索区间的左右界限 \(L\) 和 \(R\)。
盘算中点：盘算中点 \(M = L + \dfrac{R - L}{2}\)。
比较
：将目的值与中点元素进行比较。
- 若相等，返回中点位置。
- 若目的值小于中点元素，缩小搜索区间至左半部分。
- 若目的值大于中点元素，缩小搜索区间至右半部分。
重复：重复上述步骤，直到找到目的值或搜索区间为空。

开区间/闭区间 Open Interval/Closed Interval

在文章开始，先了解一下区间的开闭性。
开区间

定义：开区间表现区间的端点 不包含在区间内，用小括号 \(()\) 表现。
示例：\((2, 5)\) 表现所有介于 \(2\) 和 \(5\) 之间的数，但不包含数字 \(2\) 和 \(5\)。
闭区间

定义：开区间表现区间的端点 包含在区间内，用方括号 \([]\) 表现。
示例：\([2, 5]\) 表现所有介于 \(2\) 和 \(5\) 之间的数，而且包含数字 \(2\) 和 \(5\)。
半开区间/半闭区间

定义：半开区间或半闭区间表现区间的一个端点包含在内，另一个端点不包含在内。
示例：\((2, 5]\) 表现所有介于 \(2\) 和 \(5\) 之间的数，且包含数字 \(5\)，但不包含数字 \(2\)。
区间类型表现方式是否包含左端点 \(a\)是否包含右端点 \(b\)开区间\((a, b)\)否否闭区间\([a, b]\)是是左开右闭\((a, b]\)否是左闭右开\([a, b)\)是否区间开闭的类型 Interval Categories

在实现二分查找的时候，区间的定义是最常见的一个题目，你可能会看到过以下不同的区间开闭性的定义：

左开右开 \((\text{left}, \text{right})\)
左闭右闭 \([\text{left}, \text{right}]\)
左开右闭 \((\text{left}, \text{right}]\)
左闭右开 \([\text{left}, \text{right})\)

通常来说，我们一般会选择【左闭右开】大概【左闭右闭】的区间定义，以是本文也就偏重围绕这两个部分讲解。但对于不同的定义区间，如果稍有不慎，就容易使代码进入 死循环。
左闭右闭区间

定义：搜索区间包括 left 和 right，即 left 和 right 都可能是目的值。
退出条件：left > right，表现搜索区间为空。
左闭右闭区间的二分查找的常见写法如下：
[code]while (left

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)