【二分查找程序题】在算法学习过程中,二分查找是一个非常基础但极其重要的知识点。它不仅在数据结构课程中频繁出现,也在各类编程面试和实际开发中有着广泛的应用。今天我们就来探讨一道典型的“二分查找程序题”,帮助大家更好地理解和掌握这一经典算法。
一、什么是二分查找?
二分查找(Binary Search),也被称为折半查找,是一种在有序数组中查找特定元素的高效算法。它的基本思想是:每次将查找区间分成两部分,根据中间元素与目标值的大小关系,决定下一步是在左半部分还是右半部分继续查找,从而逐步缩小搜索范围,直到找到目标值或确定其不存在。
二分查找的时间复杂度为 O(log n),相比线性查找的 O(n) 要高效得多,尤其适合处理大规模数据。
二、典型题目解析
题目描述:
给定一个按升序排列的整数数组 `nums` 和一个目标值 `target`,请找出该目标值在数组中的第一个位置和最后一个位置。如果目标值不存在于数组中,则返回 `[-1, -1]`。
示例:
输入:`nums = [5,7,7,8,8,10]`, `target = 8`
输出:`[3,4]`
输入:`nums = [1,3,5,7,9]`, `target = 2`
输出:`[-1, -1]`
三、解题思路
要解决这个问题,我们需要两次使用二分查找:
1. 第一次查找:找到目标值的第一个出现的位置。
2. 第二次查找:找到目标值的最后一个出现的位置。
1. 查找第一个出现的位置
在常规的二分查找中,当 `nums[mid] == target` 时,我们通常直接返回 `mid`。但在这种情况下,我们需要继续向左查找,以确保找到的是第一个出现的位置。
```python
def find_first(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left if left < len(nums) and nums[left] == target else -1
```
2. 查找最后一个出现的位置
同样的逻辑,但这次我们要向右查找,确保找到的是最后一个出现的位置。
```python
def find_last(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right if right >= 0 and nums[right] == target else -1
```
四、完整代码实现
```python
def search_range(nums, target):
first = find_first(nums, target)
if first == -1:
return [-1, -1]
last = find_last(nums, target)
return [first, last]
辅助函数
def find_first(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left if left < len(nums) and nums[left] == target else -1
def find_last(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] <= target:
left = mid + 1
else:
right = mid - 1
return right if right >= 0 and nums[right] == target else -1
```
五、总结
二分查找虽然看似简单,但在实际应用中需要灵活处理各种边界条件。本题通过两次二分查找,分别找到目标值的起始和结束位置,体现了二分查找的扩展应用场景。掌握这类题目不仅能提升算法能力,也能在实际项目中更高效地处理数据查询问题。
希望这篇内容能帮助你深入理解二分查找的原理与应用!