咨询二分查找在有序数组中最优、平均、最坏情况的比较次数（含元素存在/不存在）

最优情况 #

无论目标是否存在，最优比较次数均为1次：

• 目标存在：首次比较直接命中数组中间元素。
• 目标不存在：首次比较即可判定目标超出数组取值范围（比如目标比所有元素都大/小）。

最坏情况 #

目标存在时 #

最坏需**⌈log₂N⌉**次比较（等价于⌊log₂N⌋ + 1）。此时目标处于搜索树的叶子节点位置，需逐层缩小范围直至命中。例如：

• N=7（数组长度7），最坏需3次比较；N=8，最坏需3次比较。

目标不存在时 #

最坏需**⌈log₂(N+1)⌉**次比较。此时目标位于数组的外部边界（比所有元素大或小），需遍历至搜索范围完全失效才终止。例如：

• N=7，最坏需3次比较；N=8，最坏需4次比较。

平均情况 #

目标存在时 #

平均比较次数基于二叉搜索树的节点深度统计：

• 每个元素的比较次数等于其在搜索树中的深度（根节点深度为1），将所有元素的深度求和后除以N即为平均次数。
• 若N为2ᵏ-1（完全二叉树结构），总比较次数为k*2ᵏ - (2ᵏ -1)，平均次数为(k*2ᵏ - 2ᵏ +1)/(2ᵏ -1)。比如N=7（k=3），总次数为3*8-7=17，平均17/7≈2.43次。
• 非完全二叉树场景，需按实际节点层级的数量加权求和后取均值。

目标不存在时 #

数组共有N+1个潜在的“不存在间隙”（数组前、元素间、数组后），平均次数为所有间隙的查找比较次数之和除以N+1：

• 每个间隙的比较次数等于查找终止前的最后一次比较次数。比如N=8时，9个间隙中有2个边界间隙需4次比较，7个中间间隙需3次比较，平均次数为(24+73)/9≈3.22次。

内容的提问来源于stack exchange，提问作者Arpit Jha