在本文中，我們將介紹二進制搜索相對于簡單線性搜索的優勢，并介紹它在 Java 中的實現。

1. 需要有效的搜索

假設我們在wine-selling業務和數以百萬計的買家每天都訪問我們的應用程序。

通過我們的應用程序,客戶可以過濾掉物品價格低于n美元,從搜索結果中選擇一個瓶子,并將它們添加到購物車。我們有成千上萬的用戶尋求葡萄酒價格限制每一秒。需要快速的結果。

后端,我們的算法運行的線性搜索整個列表葡萄酒比較價格限制輸入的客戶提供的價格每一個酒瓶在列表中。

然后,它返回物品的價格小于或等于價格限制。這個線性搜索時間復雜度為O (n)。

這意味著我們系統中的酒瓶數量越多，所需的時間就越多。搜索時間與引入的新項目的數量成正比。

如果我們開始按排序順序保存項目并使用二進制搜索搜索項目，我們可以實現O(log n)的復雜度。

對于二分搜索，搜索結果所花費的時間自然會隨著數據集的大小而增加，但不會成比例地增加。

2. 二分查找

簡單來說，算法將鍵值與數組的中間元素進行比較;如果它們不相等，則刪除不能包含密鑰的一半，并繼續搜索剩余的一半，直到成功。

請記住 - 這里的關鍵方面是數組已經排序。

如果搜索以剩余的一半為空而結束，則該鍵不在數組中。

(1)迭代實現

public int runBinarySearchIteratively(
  int[] sortedArray, int key, int low, int high) {
    int index = Integer.MAX_VALUE;    
    while (low <= high) {
        int mid = low  + ((high - low) / 2);
        if (sortedArray[mid] < key) {
            low = mid + 1;
        } else if (sortedArray[mid] > key) {
            high = mid - 1;
        } else if (sortedArray[mid] == key) {
            index = mid;
            break;
        }
    }
    return index;
}

runBinarySearchIteratively方法將sortedArray、key和 sortedArray 的低索引和高索引作為參數。當方法第一次運行時， sortedArray的第一個索引low為 0，而sortedArray的最后一個索引high等于其長度 - 1。

中間是sortedArray的中間索引。現在算法運行一個while循環，將鍵與sortedArray的中間索引的數組值進行比較。

注意中間索引是如何生成的(int mid = low + ((high – low) / 2)。這是為了適應非常大的數組。如果中間索引是通過獲取中間索引(int mid = (low + high) / 2) ，包含 2 30 個或更多元素的數組可能會發生溢出，因為low + high的總和很容易超過最大正int值。

(2)遞歸實現

現在，讓我們看看一個簡單的遞歸實現：

public int runBinarySearchRecursively(
  int[] sortedArray, int key, int low, int high) {
    int middle = low  + ((high - low) / 2);        
    if (high < low) {
        return -1;
    }
    if (key == sortedArray[middle]) {
        return middle;
    } else if (key < sortedArray[middle]) {
        return runBinarySearchRecursively(
          sortedArray, key, low, middle - 1);
    } else {
        return runBinarySearchRecursively(
          sortedArray, key, middle + 1, high);
    }
}

runBinarySearchRecursively方法接受sortedArray、鍵、sortedArray的低索引和高索引。

(3)使用數組。二進制搜索()

int index = Arrays.binarySearch(sortedArray, key);

將在整數數組中搜索的 sortedArray和int key作為參數傳遞給Java Arrays類的binarySearch方法。

(4)使用集合。二進制搜索()

int index = Collections.binarySearch(sortedList, key);

sortedList &整數鍵,搜索列表中的整數對象,作為參數傳遞到binarySearch Java集合類的方法。

(5)性能

是否使用遞歸迭代的方法編寫的算法主要是一個個人喜好問題。但仍有一些觀點我們應該意識到:

1)慢遞歸可以維護一個堆棧的開銷和通常要占用更多的記憶空間

2)遞歸不是stack-friendly。它可能導致StackOverflowException當處理大數據集

3)遞歸添加清晰的代碼,使其較短的迭代方法相比

理想情況下,一個二叉搜索將執行更少數量的比較與一個線性搜索大的n, n為較小的值,值的線性搜索可以執行比二進制搜索。

每個人都應該知道這個分析是理論和可能取決于上下文。

此外，二分搜索算法需要一個排序的數據集，它也有它的成本。如果我們使用歸并排序算法對數據進行排序，則會在我們的代碼中增加n log n的額外復雜度。

所以首先我們需要很好地分析我們的需求，然后決定哪種搜索算法最適合我們的需求。