折半查找和顺序查找的实现以及对比次数c语言
时间: 2024-04-30 16:18:14 浏览: 9
折半查找(二分查找)的实现:
```c
int binarySearch(int arr[], int left, int right, int x) {
int mid;
while (left <= right) {
mid = left + (right - left) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] < x) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // 找不到返回-1
}
```
顺序查找的实现:
```c
int sequentialSearch(int arr[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
}
}
return -1; // 找不到返回-1
}
```
折半查找和顺序查找的对比次数:
折半查找的平均对比次数为 log2(n),其中n为元素个数。
顺序查找的平均对比次数为 n/2,其中n为元素个数。
所以当n很大时,折半查找的效率比顺序查找高。
相关问题
C语言顺序查找法和折半查找法代码实现
以下是C语言实现顺序查找和折半查找的代码实现:
1. 顺序查找
```c
#include <stdio.h>
int SeqSearch(int r[], int n, int k) {
r[0] = k; // 下标0用作哨兵存放待查找的元素
int i;
for (i = n; r[i] != k; i--); // 从后往前查找
return i; // 返回查找到的元素下标,未找到返回0
}
int main() {
int r[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(r) / sizeof(int) - 1; // 数组长度
int k = 5; // 待查找元素
int index = SeqSearch(r, n, k);
if (index) {
printf("找到元素%d了,在第%d个\n", k, index);
} else {
printf("找不到该元素%d\n", k);
}
return 0;
}
```
2. 折半查找
```c
#include <stdio.h>
int BinSearch(int r[], int n, int k) {
int low = 1, high = n, mid;
while (low <= high) {
mid = (low + high) / 2;
if (r[mid] == k) {
return mid;
} else if (r[mid] > k) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return 0; // 未找到返回0
}
int main() {
int r[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int n = sizeof(r) / sizeof(int) - 1; // 数组长度
int k = 5; // 待查找元素
int index = BinSearch(r, n, k);
if (index) {
printf("找到元素%d了,在第%d个\n", k, index);
} else {
printf("找不到该元素%d\n", k);
}
return 0;
}
```
用c语言实现顺序表的顺序和折半查找
顺序表是一种线性表,可以使用数组来实现。顺序查找和折半查找是两种常见的查找算法。
以下是用c语言实现顺序表的顺序查找和折半查找的示例代码:
```c
#include <stdio.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int length;
} SeqList;
// 初始化顺序表
void initList(SeqList* list) {
list->length = 0;
}
// 向顺序表中插入元素
void insert(SeqList* list, int value) {
if (list->length == MAX_SIZE) {
printf("List is full.\n");
return;
}
list->data[list->length++] = value;
}
// 顺序查找
int seqSearch(SeqList* list, int value) {
for (int i = 0; i < list->length; i++) {
if (list->data[i] == value) {
return i;
}
}
return -1;
}
// 折半查找
int binarySearch(SeqList* list, int value) {
int low = 0, high = list->length - 1, mid;
while (low <= high) {
mid = (low + high) / 2;
if (list->data[mid] == value) {
return mid;
} else if (list->data[mid] > value) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
int main() {
SeqList list;
initList(&list);
insert(&list, 1);
insert(&list, 3);
insert(&list, 5);
insert(&list, 7);
insert(&list, 9);
int index = seqSearch(&list, 5);
if (index != -1) {
printf("Found at index %d.\n", index);
} else {
printf("Not found.\n");
}
index = binarySearch(&list, 5);
if (index != -1) {
printf("Found at index %d.\n", index);
} else {
printf("Not found.\n");
}
return 0;
}
```
在上面的示例代码中,我们定义了一个SeqList结构体来表示顺序表,包含一个数组和一个长度属性。我们使用initList函数来初始化顺序表,使用insert函数来向顺序表中插入元素。顺序查找使用seqSearch函数来实现,折半查找使用binarySearch函数来实现。