二分查找算法

枚举查找也就是顺序查找。

实现原理就是逐个比较 a[0:n-1] 中的元素，直到找出元素 x 或搜索遍整个数组后确定 x 不在其中，或者说符合要求的元素在不在数组中。

最坏的情况下需要比较 N 次，时间复杂度是 O(n) 线性阶。

二分查找也就是折半查找。折半查找是将 N 个元素分成大致相同的两部分。选取中间元素与查找的元素比较，或者与查找条件相比较，找到或者说找到下一次查找的半区。每次都将范围缩小至1/2​ 所以时间复杂度是 O(log2n），但是二分查找的前提是有序的，一般是从小到大排列。且一般用于查<=x的max值或>=x的min值。

折半查找的基本思想：

在有序表中（low,high,low<=high），取中间记录即 [(high+low)/2] 作为比较对象。

• 若给定值与中间记录的关键码相等，则查找成功
• 若给定值小于中间记录的关键码，则在中间记录的左半区继续查找
• 若给定值大于中间记录的关键码，则在中间记录的右半区继续查找

不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。

二分查找的特征：

1. 答案具有单调性；
2. 二分答案的问题往往有固定的问法，比如：令最大值最小（最小值最大），求满足条件的最大（小）值等。

折半查找一般过程：

本文地址：http://sjzytwl.xhstdz.com/quote/3979.html    物流园资讯网 http://sjzytwl.xhstdz.com/ , 查看更多