Java中的線性搜索一直是在數(shù)組中查找元素的首選方法。它按順序搜索數(shù)組的每個(gè)元素，并且非常容易實(shí)現(xiàn)。但是，當(dāng)所討論的數(shù)組包含數(shù)萬個(gè)元素時(shí)，線性搜索的缺點(diǎn)是顯而易見的。在這種情況下，Binary Search實(shí)現(xiàn)的“分而治之”方法對(duì)于具有時(shí)間和空間復(fù)雜性的程序員來說更加有效和可取。

　　二進(jìn)制搜索

　　在二進(jìn)制搜索中，數(shù)組被反復(fù)分成兩半，直到找到鍵(正在搜索的元素)。分割是虛擬的，即保持?jǐn)?shù)據(jù)的完整性。每次迭代時(shí)，數(shù)組的中間值都是集中的。如果該值等于我們正在尋找的鍵，則循環(huán)或遞歸函數(shù)終止。否則，它會(huì)繼續(xù)循環(huán)。如果中間值大于鍵，則該函數(shù)將焦點(diǎn)放在數(shù)組的前半部分，反之亦然。重復(fù)此過程，直到找到密鑰或循環(huán)訪問整個(gè)陣列。

　　線性搜索和二進(jìn)制搜索之間的區(qū)別

　　二進(jìn)制搜索算法

　　二進(jìn)制搜索的算法如下。

　　確定陣列的第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)。每次迭代時(shí)，這些點(diǎn)將根據(jù)數(shù)組和正在搜索的鍵進(jìn)行調(diào)整。

　　循環(huán)訪問數(shù)組并比較當(dāng)前第一個(gè)點(diǎn)和最后一個(gè)點(diǎn)之間的中間值。在第一次迭代中，第一個(gè)和最后一個(gè)變量將與數(shù)組中的實(shí)際變量相同。

　　如果鍵大于中間值，則該值的索引將存儲(chǔ)在新的“First”變量中。

　　如果鍵小于中間值，則該值的索引將存儲(chǔ)在“Last”變量中。

　　重復(fù)此條件，直到以下兩個(gè)條件之一變?yōu)檎妫?/p>

　　找到密鑰。

　　已迭代整個(gè)數(shù)組。

　　下面給出了迭代二進(jìn)制搜索和遞歸二進(jìn)制搜索的代碼。

　　迭代二進(jìn)制搜索

　　下面給出了使用迭代方法進(jìn)行二進(jìn)制搜索的代碼。

　　遞歸二進(jìn)制搜索

　　下面給出了使用遞歸的二進(jìn)制代碼。

　　時(shí)間復(fù)雜度

　　隨著每次迭代的傳遞，數(shù)組(即搜索空間)被拆分一半。每次迭代“m”后，搜索空間的大小將更改為N / 2m。在最壞的情況下，我們只會(huì)在數(shù)組的一個(gè)遠(yuǎn)端留下一個(gè)元素。此時(shí)，二進(jìn)制搜索的復(fù)雜性將是 k = log2N。線性搜索的時(shí)間復(fù)雜度為O(N)，這導(dǎo)致二進(jìn)制搜索的速度比O(log2N)復(fù)雜度快得多。這是使用二進(jìn)制搜索而不是線性搜索的主要好處。

　　空間復(fù)雜性

　　二進(jìn)制搜索使用三個(gè)不同的變量 - 開始，結(jié)束和中間。這三個(gè)變量被創(chuàng)建為指向數(shù)組索引的內(nèi)存位置的指針。因此，二進(jìn)制搜索在空間方面非常有效。迭代二進(jìn)制搜索的空間復(fù)雜度為 O(1)。對(duì)于遞歸實(shí)現(xiàn)，它是 O(log N)。