编写程序实现顺序查找和折半查找。
时间: 2024-02-19 07:57:16 浏览: 35
顺序查找(线性查找)的程序实现示例:
```python
def sequential_search(arr, target):
"""
在列表 arr 中查找目标元素 target,返回其下标,若不存在则返回 -1
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
```
折半查找(二分查找)的程序实现示例:
```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:
right = mid - 1
else:
left = mid + 1
return -1
```
以上是 Python 代码示例,其他语言的实现类似。
相关问题
编写程序实现顺序查找和折半查找
好的,以下是顺序查找和折半查找的 Python 代码实现:
## 顺序查找
def sequential_search(lst, item):
# 从列表的第一个元素开始遍历
for i in range(len(lst)):
# 如果当前元素等于查找的元素,则返回该元素的下标
if lst[i] == item:
return i
# 如果没有找到,则返回 -1
return -1
## 折半查找
def binary_search(lst, item):
# 定义左右两个指针
left = 0
right = len(lst) - 1
# 只要左指针小于等于右指针,就继续查找
while left <= right:
# 计算中间位置
mid = (left + right) // 2
# 如果中间位置的元素等于查找的元素,则返回该元素的下标
if lst[mid] == item:
return mid
# 如果中间位置的元素大于查找的元素,则在左半部分继续查找
elif lst[mid] > item:
right = mid - 1
# 如果中间位置的元素小于查找的元素,则在右半部分继续查找
else:
left = mid + 1
# 如果没有找到,则返回 -1
return -1
用C语言编写程序实现顺序查找和折半查找
以下是C语言实现顺序查找和折半查找的示例代码:
### 顺序查找
```c
#include <stdio.h>
int seq_search(int arr[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1;
}
int main() {
int arr[] = {2, 4, 7, 8, 10, 12};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 8;
int index = seq_search(arr, n, x);
if (index == -1) {
printf("%d not found", x);
} else {
printf("%d found at index %d", x, index);
}
return 0;
}
```
### 折半查找
```c
#include <stdio.h>
int binary_search(int arr[], int low, int high, int x) {
while (low <= high) {
int mid = (low + high) / 2;
if (arr[mid] == x) {
return mid;
} else if (arr[mid] < x) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return -1;
}
int main() {
int arr[] = {2, 4, 7, 8, 10, 12};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 8;
int index = binary_search(arr, 0, n-1, x);
if (index == -1) {
printf("%d not found", x);
} else {
printf("%d found at index %d", x, index);
}
return 0;
}
```