二分查找(有序链表可以二分查找吗)

一、二分查找用什么数据类型

二分法就是一种在有序数组中查找某一特定元素的搜索算法。

二、二分法最多查找次数怎么求

二分法最多查找次数可以通过以下公式求得：最多查找次数=log2(n)，其中n为有序数组的元素个数。这是因为在每一次比较后，二分法都会将待查找的范围缩小一半，直到找到目标元素或范围缩小到只剩一个元素。例如，如果有一个有序数组包含16个元素，则最多需要进行log2(16)=4次比较。需要注意的是，该公式是在最坏情况下的最大查找次数。在实际情况中，由于数组元素的分布并不总是均匀的，可能会出现最多查找次数超过该公式所得结果的情况。

三、二分法次数计算公式

（n+1）/2=5.5

1次,精度1

2次精度0.5

3次精度0.25

4次精度0.125

5次精度0.0625

所以5次

可以使用画二叉判定树的方法来分析。该二叉判定树的高度为[log2(n)]+1层，此即为二分查找的最多比较次数，比如：n=1000，则最多比较[log2(1000)]+1=9+1=10次。

如果要计算平均的比较次数，则需要对二叉判定树中的每个节点进行分析，处于第一层的比较1次，第二层的比较2次，第三层比较3次，依次类推……把各个节点的比较次数累加，再处于节点数（元素个数）即为平均比较次数，这里假设查找是在等概率的情况下进行的。