數據結構與算法——二分查找

boredream 發布于2019-08-16 16:02 / 2897人閱讀

摘要：所以，二分查找較適用于一次排序，多次查找的數據。面對大量的數據，二分查找方能體現其優勢。

1. 二分查找的思想

二分查找是一種使用十分普遍的查找算法，其基本的思路也非常的簡單，在一個有序的數據集合中，我們想要查找某個數據，直接取最中間的那個數據，將它和要找的數據進行比較，如果較大，則在更大的那個數值區間繼續取中間值查找，反之亦然。

例如我們要在一個有序的集合里[1，3，5，6，7，8，10]，查找5這個值，那么二分查找的過程就如下圖所示，經過三次查找操作就能夠找到。

2. 二分查找的實現

相信你已經能夠理解二分查找的思路了，接下來看看它的代碼實現。其實根據思路不難看出，二分查找有點分治的思想，所以代碼可以用遞歸實現，也可以用循環實現。

二分查找的遞歸實現：

public class BinarySearch {

    public static int binarySearchByRecursion(int[] data, int value) {
        return binarySearchInternally(data, 0, data.length - 1, value);
    }

    private static int binarySearchInternally(int[] data, int low, int high, int value) {
        while (low <= high){
            //計算中間值
            int mid = low + ((high - low) >> 1);

            if (data[mid] == value) return mid;
            else if (data[mid] < value) return binarySearchInternally(data, mid + 1, high, value);
            else return binarySearchInternally(data, low, mid - 1, value);
        }
        return -1;
    }
}

二分查找循環實現：

    public static int binarySearchByCircle(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;

        while (low <= high){
            //計算中間值
            int mid = low + ((high - low) >> 1);
            if (data[mid] == value) return mid;
            else if (data[mid] < value) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

3. 二分查找的局限性

二分查找是一種很高效的算法，時間復雜度為 O(logn)，要是使用上的話，非常的方便。但是，二分查找對數據的要求也十分嚴苛。

首先，二分查找只適用于順序表結構，說簡單點，就是數組。因為可以利用數組下標訪問的特性，快速取出數據進行比較。其他的數據結構例如鏈表，如果使用二分查找的話，不能進行下標訪問，每次比較都必須遍歷鏈表尋找中間節點，時間復雜度就很高了。

其次，二分查找針對的是有序數組，如果數據未排序，則必須進行排序才能夠使用，前面說到了，排序的時間復雜度一般為 O(nlogn)。所以，二分查找較適用于一次排序，多次查找的數據。如果數據的插入和刪除操作過于頻繁，那么維護有序的成本就很高。

最后，二分查找適用于數據量較大的場景，假如我們要在幾十或者幾百個數據中進行查找，那直接遍歷查找即可。面對大量的數據，二分查找方能體現其優勢。

GPU云服務器云服務器二分查找二分查找代碼二分法查找二分查找c語言實例

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/73858.html

數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

zsirfs 2019-08-23 15:33 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

you_De 2019-08-16 15:26 評論0 收藏0
數據結構與算法：二分查找

摘要：為檢查長度為的列表，二分查找需要執行次操作。最后需要指出的一點是高水平的讀者可研究一下二叉樹關于二叉樹，戳這里數據結構與算法二叉樹算法常見練習在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。常見數據結構簡單數據結構（必須理解和掌握）有序數據結構：棧、隊列、鏈表。有序數據結構省空間（儲存空間小）無序數據結構：集合、字典、散列表，無序...

gotham 2019-07-31 10:07 評論0 收藏0
【二分查找】| 模擬 20 萬數據快速查詢 IP 歸屬地

摘要：通過兩個二分查找的條件繼續進行問題的分析，那么問題又來了，二分查找是快速的查找一個數據是否存在一組數據中，而且效率極高，億查找一個數據只需次查找。二分查找的三點重點循環退出條件注意是而不是。 showImg(https://segmentfault.com/img/remote/1460000018761246);這篇文章主要深入數據結構與算法在解決實際問題怎么運用和分析的，對于 IP...

The question 2019-08-23 16:44 評論0 收藏0
數據結構與算法——二分查找練習

摘要：查找最后一個等于給定值的元素這種變形的二分查找和上面的這種情況很類似，還是利用上面的那個數組，我們要查找最后一個等于的元素。 1. 概述前面說到了二分查找問題，看起來非常的簡單，的確，前面的兩種實現都不難，代碼也很容易寫，因為那只是最基礎的二分查找問題了。今天來看看幾種稍微復雜的二分查找問題：查找第一個等于給定值的元素查找最后一個等于給定值的元素查找第一個大于等于給定值的元素...

JasinYip 2019-08-16 16:05 評論0 收藏0