简介

也称折半搜索算法（英语：half-interval search algorithm）对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法

时间复杂度

\log_2N

平均查找长度

ASL= \log_2(n+1)-1

二分算法的原理

在任意一个升序排列的表/数组/集合中，查找一个 元素 P，
在初始状态下，查找区域为整张表，
用 low 记录区域内第一个元素的位置，
用_ high _记录第一个元素的位置，
借助下列公式，取其中间元素 Q

Q=\dfrac{\left(low+high\right)}{2}

若 Q≠P，则：
Q>Q 时，将 Q 设为_ high，_查找范围变更为从 low 至 high（Q）（Q 左侧）
P>Q 时，将 Q 设为 low，查找范围变更为从 low（Q）至 high（Q 右侧）
直至 Q=P
或

low=high=P