在97个记录的由于顺序表中进行二分查找,最大比较次数是?

发布网友 发布时间：2022-05-17 13:35

我来回答

共3个回答

热心网友 时间：2023-10-23 07:55

在97个记录的由于顺序表中进行二分查找，最大比较次数是7次。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

根据顺序表二分法查找比较次数的计算公式：

当顺序表有n个关键字时：

查找失败时，至少比较a次关键字；查找成功时，最多比较关键字次数是b。

所以，当顺序表记录数 n=97 时，log₂64<log₂97<log₂128，即6<log₂97<7，最大比较次数为7次。

扩展资料

算法要求：

1、必须采用顺序存储结构。

2、必须按关键字大小有序排列。

在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素,称作线性表的顺序存储结构。

由此得到的存储结构为顺序存储结构，通常顺序存储结构是借助于计算机程序设计语言（例如c/c++）的数组来描述的。

顺序存储结构的主要优点是节省存储空间，因为分配给数据的存储单元全用存放结点的数据（不考虑c/c++语言中数组需指定大小的情况），结点之间的逻辑关系没有占用额外的存储空间。

采用这种方法时，可实现对结点的随机存取，即每一个结点对应一个序号，由该序号可以直接计算出来结点的存储地址。

但顺序存储方法的主要缺点是不便于修改，对结点的插入、删除运算时，可能要移动一系列的结点。

优点：随机存取表中元素、储存密度大。

缺点：插入和删除操作需要移动元素。

参考资料：百度百科-二分查找

参考资料：百度百科-顺序存储结构

热心网友 时间：2023-10-23 07:55

在97个记录的由于顺序表中进行二分查找，最大比较次数是7次。

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

根据顺序表二分法查找比较次数的计算公式：

当顺序表有n个关键字时：

查找失败时，至少比较a次关键字；查找成功时，最多比较关键字次数是b。

所以，当顺序表记录数 n=97 时，log₂64<log₂97<log₂128，即6<log₂97<7，最大比较次数为7次。

扩展资料：

二分查找的基本思想：

将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2]，则找到x,算法中止；如果x<a[n/2]，则只要在数组a的左半部分继续搜索x，如果x>a[n/2]，则只要在数组a的右半部搜索x。

时间复杂度无非就是while循环的次数，若总共有n个元素，则时间复杂度可以表示为O(h)=O(log2n)。

参考资料来源：百度百科-二分查找

热心网友 时间：2023-10-23 07:56