首页 > 网络 > 精选范文 >

二分查找程序题

2025-07-09 03:18:54

问题描述:

二分查找程序题,有没有大神路过?求指点迷津!

最佳答案

推荐答案

2025-07-09 03:18:54

二分查找程序题】在算法学习过程中,二分查找是一个非常基础但极其重要的知识点。它不仅在数据结构课程中频繁出现,也在各类编程面试和实际开发中有着广泛的应用。今天我们就来探讨一道典型的“二分查找程序题”,帮助大家更好地理解和掌握这一经典算法。

一、什么是二分查找?

二分查找(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

```

五、总结

二分查找虽然看似简单,但在实际应用中需要灵活处理各种边界条件。本题通过两次二分查找,分别找到目标值的起始和结束位置,体现了二分查找的扩展应用场景。掌握这类题目不仅能提升算法能力,也能在实际项目中更高效地处理数据查询问题。

希望这篇内容能帮助你深入理解二分查找的原理与应用!

免责声明:本答案或内容为用户上传,不代表本网观点。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。 如遇侵权请及时联系本站删除。