01. 二分查找知识(一)
01. 二分查找知识(一)
1. 二分查找算法介绍
1.1 二分查找算法简介
二分查找算法(Binary Search Algorithm):也叫做折半查找算法、对数查找算法,是一种用于在有序数组中查找特定元素的高效搜索算法。
二分查找的基本算法思想为:通过确定目标元素所在的区间范围,反复将查找范围减半,直到找到元素或找不到该元素为止。
1.2 二分查找算法步骤
以下是二分查找算法的基本步骤:
初始化:首先,确定要查找的有序数据集合。可以是一个数组或列表,确保其中的元素按照升序或者降序排列。
确定查找范围:将整个有序数组集合的查找范围确定为整个数组范围区间,即左边界
和右边界 。计算中间元素:根据
计算出中间元素下标位置 。比较中间元素:将目标元素
与中间元素 进行比较:- 如果
,说明找到 ,因此返回中间元素的下标位置 。 - 如果
,说明目标元素在左半部分( ),更新右边界为中间元素的前一个位置,即 。 - 如果
,说明目标元素在右半部分( ),更新左边界为中间元素的后一个位置,即 。
- 如果
重复步骤
,直到找到目标元素时返回中间元素下标位置,或者查找范围缩小为空(左边界大于右边界),表示目标元素不存在,此时返回 。
举个例子来说,以在有序数组
- 确定查找范围:初始时左边界
(数组的起始位置), (数组的末尾位置)。此时查找范围为 。 - 计算中间元素:中间元素下标位置
,对应元素为 。 - 比较中间元素:因为
,所以目标元素可能在右半部分,更新左边界为中间元素的后一个位置,即 。此时查找范围为 。 - 计算中间元素:中间元素下标位置
,对应元素为 。 - 比较中间元素:因为
,所以目标元素可能在左半部分,更新右边界为中间元素的前一个位置,即 。此时查找范围为 。 - 计算中间元素:中间元素下标位置
(向下取整),对应元素为 。 - 比较中间元素:因为
,正好是我们正在查找的目标元素,此时返回中间元素的下标位置,算法结束。
于是我们发现,对于一个长度为
::: tabs#BinarySearch
@tab <1>
@tab <2>
@tab <3>
@tab <4>
@tab <5>
@tab <6>
@tab <7>
@tab <8>
:::
1.2 二分查找算法思想
二分查找算法是经典的 「减而治之」 的思想。
这里的 「减」 是减少问题规模的意思,「治」 是解决问题的意思。「减」 和 「治」 结合起来的意思就是 「排除法解决问题」。即:每一次查找,排除掉一定不存在目标元素的区间,在剩下可能存在目标元素的区间中继续查找。
每一次通过一些条件判断,将待搜索的区间逐渐缩小,以达到「减少问题规模」的目的。而于问题的规模是有限的,经过有限次的查找,最终会查找到目标元素或者查找失败。
2. 简单二分查找
下面通过一个简单的例子来讲解下二分查找的思路和代码。
- 题目链接:704. 二分查找
2.1 题目大意
描述:给定一个升序的数组
要求:返回
说明:
- 你可以假设
中的所有元素是不重复的。 将在 之间。 的每个元素都将在 之间。
示例:
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
2.2 解题思路
思路 1:二分查找
- 设定左右边界为数组两端,即
, ,代表待查找区间为 (左闭右闭区间)。 - 取两个节点中心位置
,先比较中心位置值 与目标值 的大小。- 如果
,则返回中心位置。 - 如果
,则将左节点设置为 ,然后继续在右区间 搜索。 - 如果
,则将右节点设置为 ,然后继续在左区间 搜索。
- 如果
- 如果左边界大于右边界,查找范围缩小为空,说明目标元素不存在,此时返回
。
思路 1:代码
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
# 在区间 [left, right] 内查找 target
while left <= right:
# 取区间中间节点
mid = (left + right) // 2
# 如果找到目标值,则直接返回中心位置
if nums[mid] == target:
return mid
# 如果 nums[mid] 小于目标值,则在 [mid + 1, right] 中继续搜索
elif nums[mid] < target:
left = mid + 1
# 如果 nums[mid] 大于目标值,则在 [left, mid - 1] 中继续搜索
else:
right = mid - 1
# 未搜索到元素,返回 -1
return -1
思路 1:复杂度分析
- 时间复杂度:
。 - 空间复杂度:
。
来源:https://github.com/itcharge/LeetCode-Py