用折半查找法在(05 13 19 21 37 56 64 75 80 88 92)表中査找元素21。
时间: 2023-06-12 08:05:28 浏览: 27
折半查找法(又称二分查找)的基本思路是:在有序表中,取中间位置的记录进行比较,如果查找的值等于中间位置的记录的关键字,则查找成功;否则利用中间位置记录将查找区间缩小一半,继续进行查找,直到找到或者查找区间为空为止。
按照这个思路,我们可以按照以下步骤查找元素21:
1. 确定查找区间的起始位置start和结束位置end,初始时start=0,end=10-1=9。
2. 计算中间位置mid,mid=(start+end)/2=4。
3. 比较中间位置记录的关键字37和要查找的值21,发现21小于37,因此需要在前半部分继续查找。
4. 更新查找区间的结束位置end=mid-1=3。
5. 计算新的中间位置mid=(start+end)/2=1。
6. 比较中间位置记录的关键字13和要查找的值21,发现21大于13,因此需要在后半部分继续查找。
7. 更新查找区间的起始位置start=mid+1=2。
8. 计算新的中间位置mid=(start+end)/2=5。
9. 比较中间位置记录的关键字56和要查找的值21,发现21小于56,因此需要在前半部分继续查找。
10. 更新查找区间的结束位置end=mid-1=4。
11. 计算新的中间位置mid=(start+end)/2=3。
12. 比较中间位置记录的关键字21和要查找的值21,发现相等,查找成功。
因此,元素21在给定表中的位置是第4个,即索引值为3。
相关问题
用折半查找法在(05 13 19 21 37 56 64 75 80 88 92)表中查找元素21。
### 回答1:
题目中给定了一组数字:05 13 19 21 37 56 64 75 80 88 92,需要在表中查找元素21。
答案:在表中查找元素21可以通过以下步骤完成:
1. 将给定的数字转化为十进制数:0x05、0x13、0x19、0x21、0x37、0x56、0x64、0x75、0x80、0x88、0x92。
2. 在表中查找元素21,即在十进制数为21的位置查找对应的字节。根据表中所给的,十进制数为21对应的字节为0x15。
注:该题给出的是一个十六进制字符串,需要将其转换为对应的十进制数进行查找。
### 回答2:
要使用折半查找法在(05 13 19 21 37 56 64 75 80 88 92)表中查找元素21,首先需要确定表的长度和目标元素的位置范围。
该表长度为11,因此范围为1至11,目标元素21的位置在第4个位置。
接下来,需要确定查找的起始和终止位置。
首先,起始位置为表的第1个位置,也就是1。
然后,将起始位置加上终止位置,并折半(取整),得到新的中间位置。
由于21的位置在第4个位置,因此需要在新的中间位置左边找,即将终止位置设为中间位置减1。
再次将起始位置加上终止位置,并折半,得到新的中间位置。
此时,将起始位置设为中间位置加1,再次折半,得到新的中间位置。
由于21即为中间位置,因此查找结束。
因此,用折半查找法在(05 13 19 21 37 56 64 75 80 88 92)表中查找元素21的过程为:确定范围和起始位置,折半查找,直到找到目标元素。
### 回答3:
折半查找法,也被称为二分查找法,是一种高效的查找方法,特别适用于有序表中查找元素。在本题中,我们需要在一个已经排好序的表中查找元素21。
步骤如下:
1. 定义两个指针,分别指向表的起始位置和结束位置,即左指针l和右指针r。
2. 计算中间位置m,即m=(l+r)/2,并取出表中第m个元素。
3. 如果查找的元素等于第m个元素,则返回该元素所在的位置。
4. 如果查找的元素小于第m个元素,则将右边界r移到m-1的位置。
5. 如果查找的元素大于第m个元素,则将左边界l移到m+1的位置。
6. 重复执行步骤2-5,知道找到该元素或者l>r结束查找。
按照上述步骤,我们可以按照如下方式在给定的表中查找元素21:
l=1, r=11, m=(l+r)/2=6.此时表中第6个元素为56,21小于56,因此右边界r移到m-1=5的位置。
l=1, r=5, m=(l+r)/2=3.此时表中第3个元素为19,21大于19,因此左边界l移到m+1=4的位置。
l=4, r=5, m=(l+r)/2=4.此时表中第4个元素为21,找到要查找的元素,返回该元素所在的位置。
因此,在给定的表中查找元素21的位置为4。
总结一下,折半查找法的时间复杂度为O(logn),效率高于顺序查找法,尤其在大规模数据查找中,显著提高查找效率。
用折半查找法在(05 13 19 21 37 56 64 75 80 88 92)表中査找元素21。程序
以下是使用折半查找法在给定的表中查找元素21的程序:
```c
#include <stdio.h>
int main() {
int arr[] = {5, 13, 19, 21, 37, 56, 64, 75, 80, 88, 92};
int n = sizeof(arr) / sizeof(arr[0]);
int left = 0, right = n - 1, mid;
while (left <= right) {
mid = (left + right) / 2;
if (arr[mid] == 21) {
printf("元素21在表中的索引为:%d\n", mid);
break;
} else if (arr[mid] < 21) {
left = mid + 1;
} else {
right = mid - 1;
}
}
if (left > right) {
printf("元素21不在表中\n");
}
return 0;
}
```
运行结果:
```
元素21在表中的索引为:3
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)