给定无序序列{1,3,4,34,67,8,13,25,39,23,10,41,55,66,52,21,64,76,68,789,546,23,56,90,109,143,178,967,11,19}; 先输出从小到大排序结果再查找与输入的给定关键字相同的元素,使用指定的算法进行查找,若存在则输出找到的元素在序列中的位序(第一个数位序记为1)和需要进行的比较次数,不存在则输出"No",序列位序从1到n,实现顺序查找和折半查找算法。c语言实现
时间: 2023-10-25 21:09:51 浏览: 163
好的,我来帮您解答这个问题。这是一个典型的查找算法问题,可以使用顺序查找和折半查找两种算法来解决。
首先,让我们来实现顺序查找算法。顺序查找算法的思想是从序列的第一个元素开始,依次比较每个元素和给定的关键字是否相等,如果找到了相等的元素,则返回该元素在序列中的位置,否则返回"no"。
以下是顺序查找的C语言代码实现:
```
#include <stdio.h>
int sequential_search(int array[], int length, int key, int *count) {
int i;
for (i = 0; i < length; i++) {
(*count)++;
if (array[i] == key) {
return i + 1;
}
}
return -1;
}
int main() {
int array[] = {1,3,4,34,67,8,13,25,39,23,10,41,55,66,52,21,64,76,68,789,546,23,56,90,109,143,178,967,11,19};
int length = sizeof(array) / sizeof(array[0]);
int count = 0;
int key = 23;
int index = sequential_search(array, length, key, &count);
if (index == -1) {
printf("No\n");
} else {
printf("Index: %d, Count: %d\n", index, count);
}
return 0;
}
```
接下来,让我们来实现折半查找算法。折半查找算法的思想是将序列按照大小排序,然后每次将查找区间折半,缩小查找范围,直到找到相等的元素或者查找区间为空为止。
以下是折半查找的C语言代码实现:
```
#include <stdio.h>
int binary_search(int array[], int length, int key, int *count) {
int low = 0, high = length - 1, mid;
while (low <= high) {
(*count)++;
mid = (low + high) / 2;
if (array[mid] == key) {
return mid + 1;
} else if (array[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
int main() {
int array[] = {1,3,4,34,67,8,13,25,39,23,10,41,55,66,52,21,64,76,68,789,546,23,56,90,109,143,178,967,11,19};
int length = sizeof(array) / sizeof(array[0]);
int count = 0;
int key = 23;
int index = binary_search(array, length, key, &count);
if (index == -1) {
printf("No\n");
} else {
printf("Index: %d, Count: %d\n", index, count);
}
return 0;
}
```
以上就是顺序查找和折半查找的实现代码。注意,这里的算法实现都是基于C语言的,其他编程语言的实现方式可能会有所不同。
阅读全文