Java中的二進制搜索：遞歸、迭代和Java集合

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

　　二進制搜索

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

　　線性搜索和二進制搜索之間的區別

　　二進制搜索算法

　　二進制搜索的算法如下。

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

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

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

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

　　重復此條件，直到以下兩個條件之一變為真：

　　找到密鑰。

　　已迭代整個數組。

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

　　迭代二進制搜索

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

　　遞歸二進制搜索

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

　　時間復雜度

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

　　空間復雜性

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