二分法比较次数19

发布网友发布时间：2023-10-19 22:05

共2个回答

热心网友时间：2024-12-05 00:45

二分法检索要求线性表结点按关键码值排序且以顺序方式存储。在查找时，首先与表的中间位置上结点的关键值比较，若相等则检索成功;否则根据比较结果确定下一步在表的前半部或后半部中继续进行。二分法检索的效率较高，设线性表有n个元素，则最多的检索次数为大于log2 n 的最小整数，最少的检索次数为1。

二分法检索又称折半检索，二分法检索的基本思想是设字典中的元素从小到大有序地存放在数组中，首先将给定值key与字典中间位置上元素的关键码比较，如果相等，则检索成功；否则，若key小，则在字典前半部分中继续进行二分法检索，若key大，则在字典后半部分中继续进行二分法检索。这样，经过一次比较就缩小一半的检索区间，如此进行下去，直到检索成功或检索失败。二分法检索是一种效率较高的检索方法，要求字典在顺序表中按关键码排序

热心网友时间：2024-12-05 00:45

最坏比较4次，那个答案(log2n+ 1)下取整或者（log2 (n + 1) ）上取整，就是这个表长的最坏情况下的比较次数，如果二叉树的层次从1 开始，则长度为n的有序顺序表进行二分查找，其最坏情况下需要的比较次数等于同样结点个数的完全二叉树的高度