设序列55,31,11,37,46,73,63,02,07进行排序构成有序表,,怎么进行折半查找,写出具体过程
时间: 2024-05-18 21:13:31 浏览: 7
折半查找,也称二分查找,是一种针对有序列表的查找算法。具体过程如下:
1. 首先确定要查找的值target和有序表的范围,即左边界low和右边界high。
2. 计算中间位置mid = (low + high) / 2。
3. 拿中间位置的值mid_val与target进行比较,如果mid_val等于target,则查找成功,返回mid;如果mid_val大于target,则在左半部分继续查找,即将high更新为mid-1;如果mid_val小于target,则在右半部分继续查找,即将low更新为mid+1。
4. 重复步骤2、3,直到找到target或者low > high时,查找失败。
现在我们来演示一下如何对序列55,31,11,37,46,73,63,02,07进行折半查找,假设要查找的值是11。
1. 确定target=11,low=0,high=8。
2. 计算中间位置mid = (low + high) / 2 = 4。
3. 拿中间位置的值46与11进行比较,46>11,所以在左半部分继续查找,即将high更新为mid-1=3。
4. 重复步骤2、3,此时low=0,high=3,mid=(low+high)/2=1,mid_val=31<11,所以在右半部分继续查找,即将low更新为mid+1=2。
5. 重复步骤2、3,此时low=2,high=3,mid=(low+high)/2=2,mid_val=11=11,查找成功,返回mid=2。
因此,在序列55,31,11,37,46,73,63,02,07中,值为11的元素在位置2上。
相关问题
设序列55,31,11,37,46,73,63,02,07进行排序构成有序表,在等概率情况下进行折半查找,画出折半查找树
好的,我来回答你的问题。
首先,对给定的序列进行排序,得到有序表:02,07,11,31,37,46,55,63,73。
然后,我们可以画出折半查找树,如下图所示:
```
37
/ \
11 63
/ \ / \
02 31 46 73
/ \
07 55
```
在等概率情况下进行折半查找,我们可以从根节点37开始,如果要查找的数小于37,则向左子树查找,否则向右子树查找。每次查找可以将查找区域缩小一半,因此平均查找次数为log2(n),其中n为序列中元素的个数。
希望我的回答能够帮到你。
实验数据采用随机数发生器产生,折半查找时调用排序算法建立有序序列再进行折半查找。
这种方法采用随机数生成器产生数据,然后使用排序算法对数据进行排序,最终使用折半查找算法进行查找。这种方法的优点是可以快速地生成大量测试数据,并且可以测试不同规模的数据。但是,由于数据是随机生成的,无法保证数据的有序性,因此在进行折半查找时需要先对数据进行排序,这会增加时间复杂度和空间复杂度。因此,在实际应用中,可能需要考虑其他生成数据的方法,以及不同的查找算法,以达到更好的性能。
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)