對半查找（算法）在工程測量中應用，適用于什么情況？

對半查找在計算機算法中也稱為二分查找，是計算機算法在工程測量中的典型應用。下面我們就這種算法給大家詳細講解一下。

一、兩種查找方法

在計算機算法中，查找主要有線性查找和對半查找兩種。

1、線性查找主要針對無序的數(shù)據(jù)序列。

如在12，16，23.5，17，8，23，45...的數(shù)據(jù)列中找到8這個數(shù)字；或者在skljojlkiolwiebclsopeipo...的字符序列中找到“bc”。

這種無序的序列查找只好采用線性查找了，即依次查找。可以從頭到尾開始查找，也可以從尾到頭開始查找，也可以將數(shù)據(jù)按一定間距分成幾部分來查找，最壞的情況都要查詢n次，算法復雜度為O(n)。

算法復雜度：解決某一問題的計算規(guī)模。即要進行多少次基本計算，針對不同問題，基本計算定義不同。

2、在當數(shù)據(jù)是有序的情況下，使用對半查找。

如在1，2，3.2，5，6，8，12的數(shù)據(jù)中找到數(shù)字5。如果數(shù)據(jù)是無序的，在可以依據(jù)升降序的情況將數(shù)據(jù)排序，然后再使用對半查找。并且在這個例子中有7個數(shù)據(jù)，根據(jù)你設定的非整取舍規(guī)則，對半的位置（7/2=3.5）可以為3也可以為4。

當為3時，查到3.2，小于查找對象5，前面部分舍棄，只關注后面部分。后面部分查找位置（4/2=2）找到6，大于5，后面部分舍去，只查找剩下的兩個，再查找1次即可。當為4時，則剛好查到5，一次即可找到。

算法難度：很顯然，對于對半查找，其算法復雜度為O(logn)。

二、對半查找的威力

線性查找算法的復雜度為O(n)，對半查找的算法復雜度為O(logn)，兩者有著指數(shù)級差別。為直觀起見，我們舉一個工程測量中的例子。針對一般緩和曲線長度在100左右，我們取120米來計算。

假定我們針對不同的計算精度要求，如精確到0.001或0.0001等，查找次數(shù)見下表

從上表我們可以看出，即便精確到0.01mm，最壞情況下也僅僅需要24次查找即可完成，而如果要采用線性查找，最壞情況下則需要12000000次，即1200萬次。兩者差異巨大。

也許您會認為電腦的運算速度現(xiàn)在達到每秒數(shù)億次，1200萬次又算得了什么呢？請注意，電腦的運算速度指每秒指令執(zhí)行條數(shù)，而非算法中的基本運算。在這個例子中，基本運算是指判斷多少次計算范圍，如采用坐標轉換去判斷，每一次的基本運算中則包括重新定義兩個坐標系和兩次坐標轉換以及相關比較，如采用線性查找，計算機會基本陷入假死機狀態(tài)。

現(xiàn)在，您應該明白在水準塔尺的尺面設計中為什么那樣區(qū)分了吧，為什么有些人能瞬間讀出讀數(shù)。

我們東英測繪儀器承接工程測量業(yè)務，也出售租賃測繪儀器，如果有測繪業(yè)務需要的朋友可以聯(lián)系我們，有需要購買或者租賃維修鑒定水準儀、經(jīng)緯儀、RTK等測繪儀器的用戶也可以直接電話聯(lián)系我們，我們將為你提供優(yōu)質的服務。