【二分查找程序题】在算法学习过程中，二分查找是一个非常基础但极其重要的知识点。它不仅在数据结构课程中频繁出现，也在各类编程面试和实际开发中有着广泛的应用。今天我们就来探讨一道典型的“二分查找程序题”，帮助大家更好地理解和掌握这一经典算法。
一、什么是二分查找？
二分查找（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
```
五、总结
二分查找虽然看似简单，但在实际应用中需要灵活处理各种边界条件。本题通过两次二分查找，分别找到目标值的起始和结束位置，体现了二分查找的扩展应用场景。掌握这类题目不仅能提升算法能力，也能在实际项目中更高效地处理数据查询问题。
希望这篇内容能帮助你深入理解二分查找的原理与应用！
