【知识点】二分查找的区间到底是开仍是闭？
二分查找的区间究竟是开仍是闭？
在这两个月的时刻里，我好像没有产出任何的有关常识点的文章，大多数都是题解相关的内容。以至于许多人觉得 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，表明查找区间为空。
左闭右闭区间的二分查找的常见写法如下：
while (left <= right) { // 留意是 <=
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // [mid+1, right]
} else {
right = mid - 1; // [left, mid-1]
}
}
左闭右开区间
界说：查找区间包含 left 但不包含 right，即目标值或许是 left，但不或许是 right。
退出条件：当 left == right 时，表明查找区间为空。
左闭右开区间的二分查找的常见写法如下：
while (left < right) { // 留意是 <
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1; // [mid+1, right)
} else {
right = mid; // [left, mid)
}
}
两种区间的迭代过程中的差异 Differences During Iterating
left 的更新：
- 左闭右闭：
left = mid + 1，由于mid现已被查看过了，mid+1开端的新区间仍是闭区间。 - 左闭右开：
left = mid + 1，坚持right的开区间性质。
right 的更新：
- 左闭右闭：
right = mid - 1，由于mid现已被查看过了，mid-1确保了闭区间不重复。 - 左闭右开：
right = mid，将mid扫除，确保开区间不包含right。
退出条件：
- 左闭右闭：循环完毕条件为
left > right。 - 左闭右开：循环完毕条件为
left == right。
两种区间的优缺点 Pros & Cons
左闭右闭的有点
- 直观易懂：包含
left和right的写法愈加挨近天然语言的描绘，例如 “在 \([left, right]\) 区间查找目标值”。 - 处理小区间：关于某些需求特别处理的小区间问题，左闭右闭能够更简单描绘逻辑。
左开右闭的长处
防止数组越界：运用左闭右开区间，right 永远是无效方位，不会直接拜访数组越界的索引。
逻辑一致性：左闭右开区间的规模在迭代过程中能够安稳坚持逻辑明晰，简单与数学符号对应。
代码简练：由于退出条件是 left == right，许多情况下能够直接用 left 回来成果，无需做出额定查看。
实践运用中的挑选 Choosing the Right Interval in Practice
在实践运用中，挑选运用左闭右闭仍是左闭右开区间，往往取决于具体问题的需求和个人习气。以下是一些辅导准则：
- 数组索引：在处理数组索引时，左闭右开区间愈加天然，由于数组的索引从
0到n-1，左闭右开能够防止n的无效拜访。 - 规模区分：当需求频频区分规模时，左闭右开区间的逻辑更明晰，减少了混杂和过错。
- 鸿沟条件：假如问题中涉及到清晰的鸿沟条件，如查找第一个或最终一个满意条件的元素，挑选适宜的区间类型能够简化逻辑。
典型例题剖析 Exemplars
1. 在数组中查找目标值，回来索引
左闭右闭完成：
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
左闭右开完成：
int binarySearch(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return -1;
}
2. 在有序数组中找到目标值的刺进方位
综上所述，左闭右开更适合这一场景，由于它的区间逻辑愈加贴合“鸿沟”问题：
int searchInsert(vector<int>& nums, int target) {
int left = 0, right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left; // 回来刺进方位
}
杂乱度剖析 Complexity Analysis
二分查找的时刻杂乱度为 \(O(\log_2 N)\)，空间杂乱度为 \(O(1)\)。这种高效性使得二分查找在处理大规模数据时表现出色。但是，二分查找的前提条件是数据有必要是有序的，这在某些情况下或许需求额定的排序时刻。
相关标题 Practice Problems
能够在阅览本文后自己实践一下以下标题：
- 查找最挨近的元素 在一个升序序列中，查找与给定值最挨近的元素。
- 二分法求函数的零点 已知函数在某区间内有且只要一个根，运用二分法求出该根。
- 查找 x 给定一个升序序列（元素均不重复），在该序列中查找指定的值，若存在则输出对应的下标，不然输出 \(-1\)。
- 二分查找 在 \(N\) 个从小到大摆放且不重复的整数中，快速找到指定的数字 \(t\)，若找不到则输出 \(-1\)。
