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

1. 需要有效的搜索

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

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

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

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

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

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

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

2. 二分查找

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

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

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

(1)迭代實(shí)現(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ù)。當(dāng)方法第一次運(yùn)行時(shí)， sortedArray的第一個(gè)索引low為 0，而sortedArray的最后一個(gè)索引high等于其長度 - 1。

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

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

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

現(xiàn)在，讓我們看看一個(gè)簡單的遞歸實(shí)現(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ù)組。二進(jìn)制搜索()

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

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

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

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

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

(5)性能

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

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

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

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

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

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

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

知識(shí)點(diǎn)擴(kuò)展：

二分算法步驟描述

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

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

若相等，則查找成功

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

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

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

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

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

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

最新評(píng)論