题记:
小文简单概述传统二分法及其应用,重点介绍其扩展:区间二分,二维及多维二分 !
概要:
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于业余时间撰写!不妥之处,欢迎批评指正。
分享到:
相关推荐
二分法及其matlab程序-经典.ppt
浅析二分法及其Matlab和C程序实现资料.pdf
二分法流程图1
C语言实现的二分法快速查找|二分法排序|二分法查找C#
二分法(dichotomie) 即一分为二的方法. 设[a,b]为R的闭区间. 逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的...
。。。
。。。
二分法排序算法 C语言实现 个人爱好 希望相互学习
使用二分法解线性方程二分法解线性方程二分法解线性方程
利用java二分法来计算最靠近值,通过二分法来遍历数据,得到想要最近值
c 二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法查找二分法...
二分法
VB 二分法求方程根 VB 二分法求方程根 VB 二分法求方程根
本例实现了用c语言实现了二分法求解方程。本例主要介绍用二分法求解方程f(X)=sin(x)在(-3,7)这个范围内的解C语言实现方法。 求解主要通过函数BisectRoot()来完成。该函数首先根据二分法的需要扫描根的存在 及根的...
二分法的一些总结和方法,并用word给出了一版matlab程序
二分法解方程,利用c语言实现。。。。。。。。。。。。。
二分法实现.txt二分法实现.txt二分法实现.txt
用C++程序编的二分法,通俗,容易懂,实验报告也有用!
这个是线性插值二分法的C语言编程,需要的朋友,可以下载来看一下
PT100用二分法查表计算温度