java中二分查找的长度是多少?它有哪些优缺点?

BSO 2020-09-16 08:39:42 java常见问答 8064

java的知识应用还是极其便捷的。上次已经为大家介绍过java中二分查找判定树的方法,今天再来介绍一下二分查找的平均长度是多少以及它有哪些优缺点,一起来看看吧。

一、二分查找的平均查找长度

假设内部结点的总数为n=2h-1,那么判定树是深度为h=lg(n+1)的满二叉树(深度h不计作外部结点)。树中第k层上的结点个数为2k-1,查找它们所需的比较次数是k。所以在这种概率假设下,二分查找成功时的平均查找长度为:

ASLbn≈lg(n+1)-1

二分查找在查找失败时需要比较的关键字个数不超过判定树的深度,在最坏情况下查找成功的比较次数也不超过判定树的深度。即为:[lg(n+1)]

需要注意的是, 二分查找的最坏性能和平均性能相当接近。

二、二分查找的优点

折半查找的时间复杂度为O(logn),极大地优于顺序查找的O(n)。

三、二分查找的缺点

虽然二分查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算。就算采用高效率的排序方法也要花费O(nlgn)的时间。

补充一些关于二分查找的适用情况:

1.二分查找只适用顺序存储结构。为了保持表的有序性,在顺序结构里插入和删除都必须移动大量的结点。所以,二分查找特别适用于那种一经建立就很少改动、但是有经常需要查找的线性表。

2.对于那些查找少而又经常需要改动的线性表,可以采用链表作为存储结构,进行顺序查找。链表上没有办法实现二分查找。

以上就是关于java中二分查找的长度是多少以及它有哪些优缺点的主要内容。如果你对java知识感兴趣,想要了解更多java基础以及常见问题,敬请关注奇Q工具网。

推荐阅读:

java中二分查找的思想是什么?算法实例展示

javac的结构是怎样的?它的查找类型包括哪些内容?

二分法查找(思路和实现),二分法查找是什么?