那如果这种可以构成折半查找关键字比较序列吗?180 500 200 450不能修改我给你的数据顺序
时间: 2023-06-25 17:06:12 浏览: 70
折半查找是一种在有序序列中查找特定元素的算法,因此需要先对数据进行排序。而你给我的数据序列并不是有序的,因此不能直接使用折半查找算法。
如果你不允许修改数据顺序,那么可以考虑使用其他的查找算法,比如线性查找或者哈希表。线性查找是一种简单的查找算法,它从序列的第一个元素开始遍历,直到找到目标元素或者遍历完整个序列。哈希表是一种基于哈希函数实现的查找表,可以快速地查找特定元素。不过,哈希表需要额外的空间来存储哈希表本身,而线性查找的时间复杂度较高,因此需要根据具体情况来选择合适的算法。
相关问题
简单c语言代码顺序查找【问题描述】 从键盘输入若干个关键字序列(不超过999个关键字),以0作为输入结束。编写代码实现折半查找关键字,查找成功输出关键字的位置,否则输出not found。
以下是简单的C语言代码,实现了顺序查找:
```c
#include <stdio.h>
#define MAX_SIZE 1000
int main()
{
int i, n, key;
int a[MAX_SIZE];
printf("请输入关键字序列,以0作为输入结束:\n");
// 读入关键字序列
i = 0;
do {
scanf("%d", &a[i]);
i++;
} while (a[i-1] != 0 && i < MAX_SIZE);
n = i - 1;
// 读入待查找的关键字
printf("请输入待查找的关键字:\n");
scanf("%d", &key);
// 顺序查找
for (i = 0; i < n; i++) {
if (a[i] == key) {
printf("关键字 %d 的位置为 %d\n", key, i+1);
return 0;
}
}
printf("not found\n");
return 0;
}
```
代码中先读入关键字序列,以0作为输入结束,并记录序列中关键字的个数n。然后读入待查找的关键字key,并在关键字序列中顺序查找key,找到则输出位置,否则输出not found。
1.给定关键字序列(12,13,14,15,16,17,18,19,20,21,22),叙述采用折半查找关键字 12、28的过程,并计算平均查找长度。
好的,我来回答你的问题。
首先,折半查找也叫二分查找,它是一种高效的查找算法。在使用折半查找之前,需要先将待查找的序列按照关键字递增(或递减)的顺序排列。
对于给定的关键字序列(12,13,14,15,16,17,18,19,20,21,22),如果我们要查找关键字12和28,具体过程如下:
1. 初始化查找范围的左右端点left和right,分别指向序列的第一个和最后一个元素。
初始时,left=0,right=10。
2. 计算中间位置mid,mid=(left+right)/2,即mid=5。
3. 比较待查找的关键字12和序列中间位置的关键字17,由于12<17,所以应该在序列的左半部分继续查找。
4. 更新右端点right,right=mid-1,此时right=4。
5. 重新计算中间位置mid,mid=(left+right)/2,即mid=2。
6. 比较待查找的关键字12和序列中间位置的关键字14,由于12>14,所以应该在序列的左半部分继续查找。
7. 更新右端点right,right=mid-1,此时right=1。
8. 重新计算中间位置mid,mid=(left+right)/2,即mid=0。
9. 比较待查找的关键字12和序列中间位置的关键字12,由于二者相等,查找成功,返回元素下标0。
对于关键字28,在第6步比较待查找的关键字12和序列中间位置的关键字14时,由于12<14,所以应该在序列的右半部分查找。更新左端点left,left=mid+1,此时left=3;重新计算中间位置mid,mid=(left+right)/2,即mid=6。在第9步比较待查找的关键字28和序列中间位置的关键字18时,由于28>18,应该在序列的右半部分继续查找。更新左端点left,left=mid+1,此时left=7;重新计算中间位置mid,mid=(left+right)/2,即mid=8。在第9步比较待查找的关键字28和序列中间位置的关键字20时,由于28<20,应该在序列的左半部分继续查找。更新右端点right,right=mid-1,此时right=7;重新计算中间位置mid,mid=(left+right)/2,即mid=7。在第9步比较待查找的关键字28和序列中间位置的关键字19时,由于28>19,应该在序列的右半部分继续查找。更新左端点left,left=mid+1,此时left=8;重新计算中间位置mid,mid=(left+right)/2,即mid=9。在第9步比较待查找的关键字28和序列中间位置的关键字21时,由于28<21,应该在序列的左半部分继续查找。更新右端点right,right=mid-1,此时right=8;重新计算中间位置mid,mid=(left+right)/2,即mid=8。此时left=right=8,查找失败。
平均查找长度ASL是指平均查找一个元素所需的比较次数,公式为ASL=(log2n+1)/2,其中n为序列长度。对于本题中的序列,n=11,所以ASL=(log2(11)+1)/2≈1.5。
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)