请用自己熟悉的语言编写线性表的顺序查找和二分查找
时间: 2023-07-19 13:25:31 浏览: 45
好的,我可以用Python语言为您编写线性表的顺序查找和二分查找的代码。
线性表的顺序查找代码如下:
```python
def linear_search(array, value):
for i in range(len(array)):
if array[i] == value:
return i
return -1
```
其中,array表示待查找的数组,value表示要查找的值。函数返回值为要查找的值在数组中的下标,若未找到则返回-1。
二分查找代码如下:
```python
def binary_search(array, value):
low = 0
high = len(array) - 1
while low <= high:
mid = (low + high) // 2
if array[mid] == value:
return mid
elif array[mid] < value:
low = mid + 1
else:
high = mid - 1
return -1
```
其中,array表示待查找的有序数组,value表示要查找的值。函数返回值为要查找的值在数组中的下标,若未找到则返回-1。
这些代码只是简单的示例,实际中您可能需要根据具体情况进行修改和优化。
相关问题
线性表的顺序查找与二分查找
线性表的顺序查找是一种简单的查找算法,也称为线性查找。它的基本思想是从线性表的第一个元素开始顺序扫描,直到找到给定的值或者扫描完整个线性表为止。如果找到了给定的值,则返回其在线性表中的位置;否则返回查找失败的信息。
顺序查找的时间复杂度为 O(n),其中 n 表示线性表中元素的个数。在最坏情况下,需要扫描整个线性表才能找到目标元素,因此算法的时间复杂度是线性的。
二分查找是一种更快的查找算法,也称为折半查找。它的前提是线性表中的元素必须有序排列。基本思想是通过比较目标值和中间位置元素的大小关系,将查找范围缩小一半,再在剩余的一半中继续查找,直到找到目标元素或者查找范围为空为止。
二分查找的时间复杂度为 O(log n),其中 n 表示线性表中元素的个数。每次查找都可以将查找范围缩小一半,因此算法的时间复杂度是对数级别的。但是,二分查找的前提是线性表中的元素必须有序排列,如果线性表中元素没有有序排列,则需要先进行排序,这会增加算法的时间复杂度。
写一段c语言代码,实现线性表的顺序查找和二分查找
顺序查找:
```c
#include <stdio.h>
#define MAX_SIZE 100
int linear_search(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i;
}
}
return -1;
}
int main(void) {
int arr[MAX_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 5;
int index = linear_search(arr, 10, key);
if (index == -1) {
printf("Not found\n");
} else {
printf("Found at index %d\n", index);
}
return 0;
}
```
二分查找:
```c
#include <stdio.h>
#define MAX_SIZE 100
int binary_search(int arr[], int n, int key) {
int left = 0;
int right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (arr[mid] == key) {
return mid;
} else if (arr[mid] < key) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
int main(void) {
int arr[MAX_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int key = 5;
int index = binary_search(arr, 10, key);
if (index == -1) {
printf("Not found\n");
} else {
printf("Found at index %d\n", index);
}
return 0;
}
```
注意:上述代码中的数组是有序的。