传统二分法及其扩展

题记： 小文简单概述传统二分法及其应用，重点介绍其扩展：区间二分，二维及多维二分 ！

概要：

0 排序与查找算法概述

1 传统二分法及其应用

2 区间二分法

3 二维二分

4 多维二分

5 总结

注1：转载请注明出处，小文由"nodexy"业余撰写；尊重原创，网络主张开放与分享并不等于忽略原作者，拒绝李彦宏！

注2：本文某些术语可能与他人习惯有所差别，但不影响主旨含义的领会，敬请谅解。

正文：

0 排序与查找算法概述

对于计算机科班出身者，数据结构与算法一定是学过的 ，排序与查找算法也一定是接触过的，考试必考的，项目必用的！关于常见排序与查找算法的基本原理讲解等知识，请参考高校教材！笔者只是找一个开头的话题，交代清楚背景。

算法特征：有穷性，确定性，可行性，输入，输出

算法描述：自然语言表述，伪代码，流程图

常见排序算法：插入，选择，冒泡，快速 - 改进版本等：TimSort 等

常见算法设计方法：枚举，回溯，递归，递推，迭代

查找算法：顺序查找，二分查找，哈希查找，二叉排序树查找

注： 概念性的东西要条理清楚，否则至少说明你在学校并不用心；比如我在面试过程中，如果遇到自称学习成绩优异的学生，会问“哈夫曼树和最优二叉树是不是同一种树？”

1 传统二分法及其应用

我们这里所讲的二分法，仅指查找算法中的二分查找法，而非其他领域的二分法(如 求函数零点近似值的二分法，又如 爱利亚学派芝诺四大著名悖论之一“证明运动是不可能的”的二分法)。

典型二分法的原理及其最小应用场景如下：
从一个有序(升序)数组中查找目标数值 dest：
先设置left,right分别为数组的第一个和最后一个元素值，mid 为数组中间元素值(所谓中间是以数组下标为基准)；
比较查找的目标值dest是否与left,right,mid相等：是则找到，结束；否则将dest与mid相比较；
如果dest比mid大，则更新left=mid,；如果dest比mid小，则更更新right=mid；
重新计算mid,并返回上一步继续比较，直至找到dest，或者left>=right(未找到dest)；

在应用方面，二分法的核心是对目标数组排序后，递归二分查找目标值！预处理的主要内容就是选择排序指标，然后排序！
需要注意的是，对于同一个有序数组，当目标值可能重复时，二分法也是稳定的，即找到的目标值下标永远不会发生变化。

2 区间二分法
所谓区间二分法，是相对于传统二分法而言的；
传统二分法可以从几何角度建模如下： 一个坐标轴上，有一系列点，从中查找目标点！
而区间二分法则是：一个坐标轴上，有一系列区间(开闭状态统一),从中查找目标点或目标子区间！
此处顺便提及下二维二分法：在一个二维坐标系上，有一系列闭合区域，从中查找目标点或目标轴区间或目标子区域！

对于区间二分法，主要考虑如下几个问题：
(1) 区间之间是否有overlap：
如果样本数据是有overlap的，则需要根据不同的查找目标做不同的处理：
如果查找点，无论是只要找到一个目标点所在区间即可，还是要找到所有目标点所在区间，都无需在预处理时做去重操作；
如果查找区间，则建议先去重，后二分；因为子区间可能跨越多个区间，或者被多个区间包含，含有oeverlap的数据会大大增加二分的复杂度。
(2) 区间是离散数据：如果区间是离散的，根据值域的大小，优先考虑是否有二分的必要：
如果值域较小，则可以声明一个全值域的0数组，然后遍历所有区间，对全值域0数组的对应下标做+1操作；之后遍历全值域数组获得目标点或目标区间。
如果值域较大，以致计算资源无法满足时，建议做二分查找。
此时离散数据的二分与连续数据二分基本相似，见下文。
(3) 区间是连续数据：
这里就是真正的区间二分法了 - 其基本原理和过程与传统二分法类似，只是在比较操作时，增加了复杂度：
a. 区间数据排序
b. 区间数据去重 - 消除overlap
c. 递归二分
d. 结果解析
e. 注意事项

3 二维二分
所谓二维二分，其实就是二维平面的区间二分，在两个轴向上先后分别做区间二分！几何视角描述见上一节“2区间二分法”。
通用的做法就是先对X轴做二分，锁定Y轴上的备选区域，然后根据数量级考虑是继续二分还是直接枚举比较。

4 多维二分
多维二分术语二维二分的扩展！这一点相信中学数学里经常会看到，一个法制或规律，从1到2之后，往往会做扩展，放到全集上去检验其各种特性。
当然，如果真的面对高维数据时，需要根据具体场景来选择方法；因为二分法并不是万能的，高维数据也有自身的特性。比如3维数据，可能还可以先后做3个维度的3次二分
，但如果是16维，32维，则可能不太适合了。

5 总结
列举了这么多，相信你一定会纳闷： 到底在哪些场合会遇到这么变态的问题呢？
其实，在应用领域，经常会碰到类似的问题：
比如Bioinformatics里的DNA序列上目标元件定位等，比如 GIS的目标区域定位，
及其宏观经济学领域和金融领域的一些目标值查找，以及BI领域的某些场景。
总的来说，一个基础方法或算法，如果你深谙其道，其实很容易触类旁通，扩展到更广泛的领域。

注：图示请参考： https://cacoo.com/diagrams/HQbjMFugU5vIpkbD 

小文由nodexy于业余时间撰写！不妥之处，欢迎批评指正。