在未知数组中查找目标数,代码要文字说明
时间: 2023-12-08 20:04:00 浏览: 24
以下是使用Python实现的二分查找算法,同时附有注释说明。
```python
def binary_search(arr, target):
"""
在有序数组arr中查找目标数target,返回目标数在数组中的下标,如果不存在则返回-1
"""
left, right = 0, len(arr) - 1 # 初始化左右指针,左指针指向数组起始位置,右指针指向数组末尾
while left <= right: # 当左指针小于等于右指针时,表示还存在待查找的区间
mid = (left + right) // 2 # 计算中间位置
if arr[mid] == target: # 如果中间位置的元素是目标数,直接返回下标
return mid
elif arr[mid] < target: # 如果中间位置的元素小于目标数,说明目标数在右侧区间,更新左指针
left = mid + 1
else: # 否则目标数在左侧区间,更新右指针
right = mid - 1
return -1 # 如果数组中不存在目标数,返回-1
```
该算法首先通过初始化左右指针来确定待查找的区间,然后通过计算中间位置并比较中间位置的元素与目标数的大小关系来更新左右指针,直到找到目标数或者确定目标数不存在于数组中为止。该算法的时间复杂度为O(logn),其中n为数组的长度,因为每次查找都可以将待查找区间缩小一半。