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

　　二進制搜索

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

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

　　二進制搜索算法

　　二進制搜索的算法如下。

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

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

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

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

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

　　找到密鑰。

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

　　下面給出了迭代二進制搜索和遞歸二進制搜索的代碼。

　　迭代二進制搜索

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

　　遞歸二進制搜索

　　下面給出了使用遞歸的二進制代碼。

　　時間復(fù)雜度

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

　　空間復(fù)雜性

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