当前位置：首页 > news >正文

Leetcode算法入门与数组丨5. 数组二分查找

news 2025/7/13 6:04:26

文章目录

- 1 二分查找算法
- 2 二分查找细节
- 3 二分查找两种思路
- - 3.1 直接法
  - 3.2 排除法

1 二分查找算法

二分查找算法是一种常用的查找算法，也被称为折半查找算法。它适用于有序数组的查找，并通过将待查找区间不断缩小一半的方式来快速定位目标值。

算法思想如下：

首先，确定待查找数组的起始位置（通常为数组的第一个元素）和结束位置（通常为数组的最后一个元素）。
然后，计算待查找区间的中间位置，即将起始位置和结束位置相加除以2。
比较中间位置的元素与目标值的大小关系：

如果中间位置的元素等于目标值，则查找成功，返回中间位置。
如果中间位置的元素大于目标值，则目标值可能在左半部分，将结束位置更新为中间位置的前一个位置。
如果中间位置的元素小于目标值，则目标值可能在右半部分，将起始位置更新为中间位置的后一个位置。

重复步骤2和步骤3，直到找到目标值或者待查找区间为空（起始位置大于结束位置）为止。

二分查找算法的时间复杂度为 $O(\log n)$ ，其中 $n$ 为数组的大小。由于每次查找都将待查找区间缩小一半，因此它比线性查找算法更加高效。

2 二分查找细节

区间开闭问题

左闭右闭区间：注意初始化时， $r i g h t = l e n (n u m s) - 1$ ，数组最后一个元素位置。
左闭右开区间：注意初始化时， $r i g h t = l e n (n u m s)$ ，数组最后一个元素的下一个位置。
一般情况，全部使用「左闭右闭区间」这种写法。

$mi d$ 取值问题

常见的两种取值公式

mid = (left + right) // 2   # 使用较多
mid = (left + right + 1) // 2

当待查找区间中的元素个数为奇数个，使用这两种取值公式都能取到中间元素的下标位置。
当待查找区间中的元素个数为偶数个
- mid = (left + right) // 2 能取到中间靠左边元素的下标位置。
- mid = (left + right + 1) // 2 能取到中间靠右边元素的下标位置。

出界条件的判断

两种判断方式

left <= right
left < right

left <= right，并且查找的元素不在有序数组中，则 while 语句的出界条件是 left > right，也就是 left == right + 1，写成区间形式就是 [ $r i g h t + 1$ , $r i g h t$ ]，此时待查找区间为空，待查找区间中没有元素存在，此时终止循环时，可以直接返回 −1。
left < right，并且查找的元素不在有序数组中，则 while 语句出界条件是 left == right，写成区间形式就是 [ $r i g h t$ , $r i g h t$ ]。此时区间不为空，待查找区间还有一个元素存在，我们并不能确定查找的元素不在这个区间中，此时终止循环时，如果直接返回 −1 就是错误的。

使用 left < right 的话，可以在出界之后增加一层判断，判断是否等于目标元素。

# ...while left < right:# ...return left if nums[left] == target else -1

此时，在跳出循环的时候，一定是 left == right，无需判断此时应该返回 left or right

搜索区间范围的选择

三种写法

left = mid + 1，right = mid - 1
left = mid + 1 ，right = mid
left = mid，right = mid - 1

具体哪一种写法和二分查找的两种思路有关。

思路 1：「直接法」—— 在循环体中找到元素后直接返回结果。
思路 2：「排除法」—— 在循环体中排除目标元素一定不存在区间。

3 二分查找两种思路

3.1 直接法

设定左右边界为数组两端，即 $l e f t = 0 ， r i g h t = l e n (n u m s) - 1$ ，代表待查找区间为 $[l e f t, r i g h t]$ （左闭右闭区间）。
取两个节点中心位置 $mi d$ ，先比较中心位置值 $n u m s [mi d]$ 与目标值 $t a r g e t$ 的大小。
1. 如果 $t a r g e t == n u m s [mi d]$ ，则返回中心位置。
2. 如果 $t a r g e t > n u m s [mi d]$ ，则将左节点设置为 $mi d + 1$ ，然后继续在右区间 $[mi d + 1, r i g h t]$ 搜索。
3. 如果 $t a r g e t < n u m s [mi d]$ ，则将右节点设置为 $mi d - 1$ ，然后继续在左区间 $[l e f t, mi d - 1]$ 搜索。
如果左边界大于右边界，查找范围缩小为空，说明目标元素不存在，此时返回 −1。

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1# 在区间 [left, right] 内查找 targetwhile left <= right:# 取区间中间节点mid = left + (right - left) // 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# 未搜索到元素，返回 -1return -1

3.2 排除法

设定左右边界为数组两端，即 $l e f t = 0 ， r i g h t = l e n (n u m s) - 1$ ，代表待查找区间为 $[l e f t, r i g h t]$ （左闭右闭区间）。
取两个节点中心位置 $mi d$ ，比较中心位置值 $n u m s [mi d]$ 与目标值 $t a r g e t$ 的大小，先将目标元素一定不存在的区间排除。
然后在剩余区间继续查找元素，继续根据条件排除目标元素一定不存在的区间。
直到区间中只剩下最后一个元素，然后再判断这个元素是否是目标元素。

class Solution:def search(self, nums: List[int], target: int) -> int:left, right = 0, len(nums) - 1# 在区间 [left, right] 内查找 targetwhile left < right:# 取区间中间节点mid = left + (right - left) // 2# nums[mid] 小于目标值，排除掉不可能区间 [left, mid]，在 [mid + 1, right] 中继续搜索if nums[mid] < target:left = mid + 1 # nums[mid] 大于等于目标值，目标元素可能在 [left, mid] 中，在 [left, mid] 中继续搜索else:right = mid# 判断区间剩余元素是否为目标元素，不是则返回 -1return left if nums[left] == target else -1