编写具体函数实现查找表的顺序查找与折半查找等基本操作
时间: 2024-01-22 18:21:06 浏览: 32
顺序查找:
```python
def sequential_search(arr, target):
"""
顺序查找
Args:
arr: List[int], 待查找的数组
target: int, 目标值
Returns:
int, 目标值在数组中的下标,若不存在则返回 -1
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
```
折半查找:
```python
def binary_search(arr, target):
"""
折半查找
Args:
arr: List[int], 待查找的数组(必须为有序数组)
target: int, 目标值
Returns:
int, 目标值在数组中的下标,若不存在则返回 -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
```
注意:折半查找要求待查找的数组必须为有序数组。如果数组无序,则需要先进行排序再进行查找。