二分搜尋 在计算机科学中二分查找算法英語binary search algorithm也称折半搜索算法英語halfinterval search algorithm对数搜索算法英語logarithmic search algorithm是一种在有序数组中查找某一特定元素的搜索算法搜索过程从数组的中间元素开始如果中间元素正好是要查找的元素则搜索过程结束如果某一特定元素大于或者小于中间元素则在数组大于或小于中间元素的那一半中查找而且跟开始一样从中间元素开始比较如果在某一步骤数组为空则代表找不到这种搜索算法每一次比较都使搜索范围缩小一半 二分查找算法在最坏情况英语Best worst and average case下是对数时间复杂度的需要进行 O  log  n  displaystyle Olog n 次比较操作 n displaystyle n 在此处是数组的元素数量 O displaystyle O 是大O记号 log displaystyle log  是对数二分查找算法使用常数空间对于任何大小的输入数据算法使用的空间都是一样的除非输入数据数量很少否则二分查找算法比线性搜索更快但数组必须事先被排序尽管一些特定的为了快速搜索而设计的数据结构更有效比如哈希表二分查找算法应用面更广 二分查找算法有许多种变种比如分散层叠英语fractional casacading可以提升在多个数组中对同一个数值的搜索的速度分散层叠有效的解决了计算几何学和其他领域的许多搜索问题指数搜索英语Exponential search将二分查找算法拓宽到无边界的列表二叉搜索树和B树数据结构就是基于二分查找算法的