给定一个按升序排列的整数数组nums和一个目标值target,请实现一个二分查找算法。如果目标值存在于数组中,返回它的索引,
时间: 2024-10-18 22:23:08 浏览: 18
当然可以。给定一个已排序的整数数组 `nums` 和一个目标值 `target`,二分查找(也称为折半查找)是一种非常高效的搜索算法,它的工作原理是不断将数组范围缩小一半,直到找到目标元素或者确定目标不存在于数组中。下面是步骤:
1. 初始化两个指针,`left` 为数组的第一个元素的索引,`right` 为数组的最后一个元素的索引。
2. 当 `left` 小于等于 `right` 时,继续循环:
a. 计算中间索引 `mid`,通常通过 `(left + right) // 2` 来计算。
b. 检查 `nums[mid]` 是否等于目标值 `target`:
- 如果相等,则找到了目标,返回 `mid`。
- 如果 `nums[mid]` 大于目标值,说明目标应该在数组左半部分,所以更新 `right` 为 `mid - 1`。
- 否则,如果 `nums[mid]` 小于目标值,说明目标应该在数组右半部分,所以更新 `left` 为 `mid + 1`.
3. 如果没有找到目标值,当 `left` 大于 `right` 时,返回 `-1` 表示目标值不在数组中。
这是一个经典的递归版本的二分查找伪代码:
```python
def binary_search(nums, target):
left = 0
right = len(nums) - 1
if left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
return binary_search(nums, mid+1)
else:
return binary_search(nums, left)
# 目标值不存在
return -1
```
阅读全文