对半查找（算法）在工程测量中应用，适用于什么情况？

对半查找在计算机算法中也称为二分查找，是计算机算法在工程测量中的典型应用。下面我们就这种算法给大家详细讲解一下。

一、两种查找方法

在计算机算法中，查找主要有线性查找和对半查找两种。

1、线性查找主要针对无序的数据序列。

如在12，16，23.5，17，8，23，45...的数据列中找到8这个数字；或者在skljojlkiolwiebclsopeipo...的字符序列中找到“bc”。

这种无序的序列查找只好采用线性查找了，即依次查找。可以从头到尾开始查找，也可以从尾到头开始查找，也可以将数据按一定间距分成几部分来查找，最坏的情况都要查询n次，算法复杂度为O(n)。

算法复杂度：解决某一问题的计算规模。即要进行多少次基本计算，针对不同问题，基本计算定义不同。

2、在当数据是有序的情况下，使用对半查找。

如在1，2，3.2，5，6，8，12的数据中找到数字5。如果数据是无序的，在可以依据升降序的情况将数据排序，然后再使用对半查找。并且在这个例子中有7个数据，根据你设定的非整取舍规则，对半的位置（7/2=3.5）可以为3也可以为4。

当为3时，查到3.2，小于查找对象5，前面部分舍弃，只关注后面部分。后面部分查找位置（4/2=2）找到6，大于5，后面部分舍去，只查找剩下的两个，再查找1次即可。当为4时，则刚好查到5，一次即可找到。

算法难度：很显然，对于对半查找，其算法复杂度为O(logn)。

二、对半查找的威力

线性查找算法的复杂度为O(n)，对半查找的算法复杂度为O(logn)，两者有着指数级差别。为直观起见，我们举一个工程测量中的例子。针对一般缓和曲线长度在100左右，我们取120米来计算。

假定我们针对不同的计算精度要求，如精确到0.001或0.0001等，查找次数见下表

从上表我们可以看出，即便精确到0.01mm，最坏情况下也仅仅需要24次查找即可完成，而如果要采用线性查找，最坏情况下则需要12000000次，即1200万次。两者差异巨大。

也许您会认为电脑的运算速度现在达到每秒数亿次，1200万次又算得了什么呢？请注意，电脑的运算速度指每秒指令执行条数，而非算法中的基本运算。在这个例子中，基本运算是指判断多少次计算范围，如采用坐标转换去判断，每一次的基本运算中则包括重新定义两个坐标系和两次坐标转换以及相关比较，如采用线性查找，计算机会基本陷入假死机状态。

现在，您应该明白在水准塔尺的尺面设计中为什么那样区分了吧，为什么有些人能瞬间读出读数。

我们东英测绘仪器承接工程测量业务，也出售租赁测绘仪器，如果有测绘业务需要的朋友可以联系我们，有需要购买或者租赁维修鉴定水准仪、经纬仪、RTK等测绘仪器的用户也可以直接电话联系我们，我们将为你提供优质的服务。