在本文中，我們將介紹二進制搜索相對于簡單線性搜索的優(yōu)勢，并介紹它在 Java 中的實現(xiàn)。

1. 需要有效的搜索

假設(shè)我們在wine-selling業(yè)務(wù)和數(shù)以百萬計的買家每天都訪問我們的應(yīng)用程序。

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

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

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

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

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

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

2. 二分查找

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

請記住 - 這里的關(guān)鍵方面是數(shù)組已經(jīng)排序。

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

(1)迭代實現(xiàn)

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 的低索引和高索引作為參數(shù)。當方法第一次運行時， sortedArray的第一個索引low為 0，而sortedArray的最后一個索引high等于其長度 - 1。

中間是sortedArray的中間索引?，F(xiàn)在算法運行一個while循環(huán)，將鍵與sortedArray的中間索引的數(shù)組值進行比較。

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

(2)遞歸實現(xiàn)

現(xiàn)在，讓我們看看一個簡單的遞歸實現(xiàn)：

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)使用數(shù)組。二進制搜索()

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

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

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

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

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

(5)性能

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

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

2)遞歸不是stack-friendly。它可能導(dǎo)致StackOverflowException當處理大數(shù)據(jù)集

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

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

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

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

知識點擴展：

二分算法步驟描述

① 首先確定整個查找區(qū)間的中間位置 mid = （ left + right ）/ 2

② 用待查關(guān)鍵字值與中間位置的關(guān)鍵字值進行比較；

若相等，則查找成功

若大于，則在后（右）半個區(qū)域繼續(xù)進行折半查找

若小于，則在前（左）半個區(qū)域繼續(xù)進行折半查找

③ 對確定的縮小區(qū)域再按折半公式，重復(fù)上述步驟。

最后，得到結(jié)果：要么查找成功， 要么查找失敗。折半查找的存儲結(jié)構(gòu)采用一維數(shù)組存放。 折半查找算法舉例

對給定數(shù)列（有序）{ 3,5,11,17,21,23,28,30,32,50,64,78,81,95,101}，按折半查找算法，查找關(guān)鍵字值為81的數(shù)據(jù)元素。

到此這篇關(guān)于Java二分查找算法實例詳解的文章就介紹到這了,更多相關(guān)Java二分查找算法淺析內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論