二分查找(BinarySearch)

leeon 發布于2019-08-16 13:39 / 3444人閱讀

摘要：基本思想二分查找算法的基本思想就是在一個有序的默認我們都是升序，如果是降序后面的條件置反即可數組中將要查找的值和數組中間的那個元素比較如果要找的數大于中間的元素就從中間的元素后一個元素開始到數組最后一個元素這個區間里面繼續尋找如果要找的數小

基本思想

二分查找算法的基本思想就是:

在一個有序的(默認我們都是升序，如果是降序后面的條件置反即可)數組中;

將要查找的值和數組中間的那個元素比較;

如果要找的數大于中間的元素,就從中間的元素后一個元素開始到數組最后一個元素這個區間里面繼續尋找;

如果要找的數小于中間的元素,就從0開始到此時的中間的元素這個區間內繼續尋找;

如果它們相等，那么此時我們要找的元素就是當前中間的元素，直接返回下標即可。

java代碼實現

private int binarySearch(int[] arr,int k){
        int index = -1;
        int start = 0;
        int end = arr.length;
        while (start < end){
            //  這里有可能會溢出，有兩種解決方案
            //  1、 修改為 start+(end-start)/2
            //  2、 通過位移操作，這樣也可以完成除2，在jdk源碼中使用的是這種方法
            int mid = (end + start) / 2;
            //  如果小于中間的元素就從0開始到當前中間的下標這個區間里面繼續尋找
            if (k < arr[mid]){
                end = mid;
            //  如果大于中間的元素就從當前的下標到最后一個元素這個區間里面繼續尋找
            }else if (k > arr[mid]){
                start = mid + 1;
            //  如果等于中間的元素就說明當前元素就是我們要找的下標
            }else {
                return mid;
            }
        }
        //  如果循環結束了都沒找到說明這個數組里面沒有我們要找的元素
        return -1;
    }

時間復雜度分析

最好的情況是我們要找的就是中間那個,此時的時間復雜度為O(1);

最壞的情況是我們找完最后一趟才找到甚至沒有找到,這個時候的時間復雜度為O(logN);

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

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/72094.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
【程序員必會十大算法】之二分查找算法

摘要：遞歸實現不考慮相同數二分查找，不考慮有相同數的情況遞歸找到了考慮有相同數二分查找考慮有相同元素的情況遞歸要查找的值 1.遞歸實現 ①不考慮相同數 /** * 二分查...

YFan 2021-09-24 09:48 評論0 收藏0
查找算法之二分查找法

摘要：查找算法之二分查找法思想二分查找法的思想非常簡單，對于一個有序數列，找它中間的元素，看是否是查找目標，如果不是，就看這個查找目標是小于還是大于中間元素，然后在對應的區間內重復上述過程。查找算法之二分查找法思想二分查找法的思想非常簡單，對于一個有序數列，找它中間的元素，看是否是查找目標，如果不是，就看這個查找目標是小于還是大于中間元素，然后在對應的區間內重復上述過程。算法需要注...

Jochen 2019-08-15 17:44 評論0 收藏0