用python语言实现顺序查找和折半查找
时间: 2023-04-27 13:00:05 浏览: 103
顺序查找:
顺序查找也叫线性查找,是一种简单的查找方法,从头到尾依次遍历待查找的元素,直到找到目标元素或遍历完整个序列。以下是用Python实现顺序查找的代码:
```python
def sequential_search(seq, target):
for i in range(len(seq)):
if seq[i] == target:
return i
return -1
```
其中,seq是待查找的序列,target是目标元素。函数返回目标元素在序列中的下标,如果找不到则返回-1。
折半查找:
折半查找也叫二分查找,是一种高效的查找方法,适用于有序序列。每次将待查找区间缩小一半,直到找到目标元素或区间为空。以下是用Python实现折半查找的代码:
```python
def binary_search(seq, target):
left, right = 0, len(seq) - 1
while left <= right:
mid = (left + right) // 2
if seq[mid] == target:
return mid
elif seq[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
```
其中,seq是有序序列,target是目标元素。函数返回目标元素在序列中的下标,如果找不到则返回-1。