二分查找，又称折半查找，是一种在有序顺序存储结构上进行的查找算法。它的正式定义可以概括为：在一个按关键字递增（或递减）有序排列的顺序表中，每一趟查找都将待查区间划分为两个子区间，通过将目标关键字与区间中间位置元素的关键字进行比较，确定目标可能落在左半区还是右半区，从而将查找区间缩小为原来的一半，如此反复，直至找到目标元素或区间收缩为空。
这个定义里有三个关键词需要拆开看。第一是"有序"，即表中元素的关键字必须事先排好序，这是二分查找成立的先决条件，缺一不可。第二是"顺序存储"，即元素必须存放在一片连续的存储空间中，比如数组，因为算法需要以常数时间直接访问区间中间位置的元素，链式存储虽然物理上也有"中间"位置，但无法做到O(1)的随机访问，查找效率会严重退化。第三是"折半"，即每一次比较都能排除掉大约一半的候选元素，这是它名字的由来，也是它效率超越顺序查找的根本原因。
从数据结构课程的角度看，二分查找属于静态查找表的范畴。静态查找表指的是只进行查找操作、不进行插入和删除操作的表，或者说查找过程中表的内容保持稳定。与之对应的是动态查找表，例如二叉排序树、平衡二叉树、B树这类结构，它们支持边查找边动态调整。软考命题人常常在这里设题，考静态查找表与动态查找表的区分，二分查找正是静态查找表的典型代表，考生务必把这个归属关系记牢。
二分查找能否使用，取决于三个前提条件，任何一个不满足，都不能直接套用，这是考试中反复考查的点。
第一个前提是关键字有序。表中的记录必须按照关键字从小到大或从大到小排列。有序是二分查找正确性的基石，如果表是无序的，比较中间元素之后就无法判断目标在左还是右，算法会失效。软考题目里经常出现"在无序表中用二分查找"的干扰选项，一旦识别出来就能直接排除。
第二个前提是顺序存储结构。二分查找依赖随机访问能力，需要在O(1)时间内定位到中间位置。数组天然满足这一点，而链表不满足。虽然理论上可以用跳表等结构在链表上实现类似折半的效果，但那已经是另一种数据结构的范畴，与经典的二分查找不是一回事。考试中若问"链式存储的有序表能否使用二分查找"，答案是否定的，因为定位中间元素本身就需要线性遍历。
第三个前提是数据规模相对稳定。因为二分查找要求表始终保持有序，而一旦发生插入或删除，就需要移动大量元素来维持有序性和顺序存储的连续性，维护成本很高。因此二分查找最适合"查多改少"甚至"只查不改"的场景，例如字典、词表、有序配置项这类几乎不变的数据。当表需要频繁增删时，应当改用二叉排序树等动态查找结构。
要理解二分查找的价值，必须把它和顺序查找放在一起比较。顺序查找不要求表有序，也不要求顺序存储，它从头到尾逐个比较，最坏情况下要比较n次，平均比较次数约为(n+1)/2，时间复杂度是O(n)。而二分查找每次比较都能将区间减半，最多比较⌈log2(n+1)⌉次就能确定结果，时间复杂度是O(log n)。
两者效率的差距随着n的增大急剧拉大。当n等于1024时，顺序查找最坏要比较1024次，而二分查找最多只要11次；当n扩大到百万量级时，顺序查找最坏要百万次，二分查找却只要约20次。这就是对数复杂度与线性复杂度的本质差异。软考经常用这种数量级的对比来考查考生对算法复杂度的直观理解，只要抓住"折半对应对数"这个核心，这类题就能稳稳拿分。
二分查找之所以正确，靠的是一套严格的区间收缩逻辑，这套逻辑可以用循环不变量来表述。算法维护一个待查区间[low, high]，low是区间左端下标，high是区间右端下标。每一趟取出区间中间位置mid，将目标关键字与mid位置元素比较，可能出现三种情况：相等则查找成功；目标小于中间元素，说明目标只可能落在左半区，于是把high收缩为mid减1；目标大于中间元素，说明目标只可能落在右半区，于是把low扩张为mid加1。
这里的核心不变量是：只要目标元素存在，它一定始终位于当前的[low, high]区间内。算法每一趟都保证不变量成立，区间因此不断缩小，最终要么low与high相遇后找到目标，要么low大于high表示区间为空、查找失败。这个不变量是理解二分查找的关键，也是很多边界错误产生的根源。为什么收缩时要写mid减1或mid加1而不是直接等于mid，正是为了让已排除的元素彻底移出区间，避免下一趟重复比较同一个位置，也避免了死循环。
可以举一个具体的查找过程来体会区间收缩的节奏。假设有序表中存放了15个元素，关键字从1到15升序排列，现在要查找目标关键字11。第一趟，low等于0，high等于14，mid等于7，即比较第7号位置的元素，其关键字为8，11大于8，说明目标在右半区，于是把low更新为8。第二趟，mid等于(8加14)除以2等于11，比较第11号位置的元素，关键字为12，11小于12，说明目标在左半区，把high更新为10。第三趟，mid等于(8加10)除以2等于9，比较第9号位置的元素，关键字为10，11大于10，把low更新为10。第四趟，mid等于10，比较关键字11，恰好相等，查找成功，总共比较4次。这个过程中区间从15逐步收缩到8、3、1，每一次都近乎对半，正体现了折半的效率。
如果目标不存在，过程会一直进行到low大于high为止。仍然以同样的表为例，这次要查找一个不存在的关键字，比如4.5，由于表中存放的都是整数，4.5必然查找失败，最终走到low大于high。关键点在于，失败时low所指向的位置，恰好是目标若存在时应当插入的位置，这一性质在工程中十分有用。
把二分查找每一趟可能比较的位置画成一棵二叉树，就得到判定树。判定树刻画了算法对所有可能的查找结果的分支结构：根结点是第一次比较的中间位置，根结点的左子树对应目标落在左半区的情形，右子树对应目标落在右半区的情形，如此逐层展开，直到每个叶结点对应查找失败的外结点。
判定树有几个重要性质，都是软考的高频考点。第一，含有n个结点的二分查找判定树是一棵平衡二叉树，左右子树高度之差不超过1，因为折半每次都把区间近乎对半切分。第二，判定树的高度就是二分查找最坏情况下的比较次数，等于⌈log2(n+1)⌉。第三，判定树共有n+1个失败结点，也就是外结点或空指针位置，它们均匀分布在判定树的最底层和倒数第二层，这对应查找失败的各种情形。理解了判定树，ASL的计算就有了直观的几何意义，很多看似复杂的计算题都能迎刃而解。
值得强调的是，判定树之所以是一棵接近满的二叉树，根源在于折半分割的均衡性。假设n等于2的k次方减1，例如n等于15，那么判定树恰好是一棵满二叉树，高度为4，所有成功结点分布在4层，失败结点有16个，全部集中在第4层下方。若n不是这种形式，例如n等于10，判定树则是一棵非满的平衡二叉树，最底层的失败结点数量会比上一层多。软考命题人尤其喜欢取n等于10、11、12这类不能构成满二叉树的数值来考，因为这时成功比较次数和失败比较次数会因结点分布不均而出现微妙差别，稍不留神就会算错。
平均查找长度ASL是衡量查找算法效率的核心指标，软考每年都要考它的计算。查找成功时的ASL定义为，所有元素被查找的概率乘以各自需要的比较次数之和。在等概率假设下，每个元素被查找的概率都是1/n，因此ASL等于判定树中所有内部结点（对应成功的比较位置）的深度之和除以n。
对于二分查找，当n较大时，成功查找的ASL有一个漂亮的近似公式：ASL约等于log2(n+1)减1。它的精确形式是((n+1)/n)乘以log2(n+1)再减1。这个公式的推导思路是，判定树是一棵接近满的二叉树，满二叉树每一层的结点数固定，把所有结点的深度加权求和，再除以n，就得到上述结果。
查找失败的ASL则对应外结点（失败结点）的平均深度。判定树有n+1个失败结点，等概率情况下失败ASL约等于log2(n+1)。需要注意的是，失败ASL通常比成功ASL大1左右，这个细微差别正是命题人喜欢挖的坑。考试中若问"含有11个元素的二分查找，成功查找最多比较几次"，答案是⌈log2(12)⌉等于4次，而不是想当然的3次。
为了更直观地掌握ASL的计算，不妨手算一个n等于11的实例。11个元素的判定树是一棵高度为4的平衡二叉树，各层成功结点数依次为1、2、4、4，深度分别为1、2、3、4，因此所有成功结点的深度之和为1乘1加2乘2加3乘4加4乘4，等于1加4加12加16，共33，再除以11，成功ASL约为3。这个结果落在3和4之间，与公式log2(12)减1约等于2.58相比之所以偏大，是因为n较小时判定树偏离理想的对数曲线，只有n充分大时近似公式才足够精确。考试中给具体n值求ASL，务必逐层加权求和，不要直接套近似公式，否则会在小题上失分。
插值查找是二分查找最直接的改进方向，它的出发点是对中间位置的选取进行优化。二分查找总是机械地取区间正中间，这在不均匀分布的数据上并非最优。插值查找则根据目标关键字在区间内的相对位置，按比例估算目标更可能落在哪里，其分割点由公式mid等于low加上(key减a[low])除以(a[high]减a[low])再乘以(high减low)得到。
这个公式的本质是在做一次线性插值，它假设关键字近似均匀分布，于是用目标值在最小值和最大值之间的比例来预测下标。当数据分布确实均匀时，插值查找的平均时间复杂度可以达到O(log log n)，优于二分查找的O(l
本篇完！