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

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

一、兩種查找方法

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

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

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

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

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

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

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

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

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

二、對半查找的威力

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

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

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

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

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

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