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

JasinYip 發布于2019-08-16 16:05 / 2166人閱讀

摘要：查找最后一個等于給定值的元素這種變形的二分查找和上面的這種情況很類似，還是利用上面的那個數組，我們要查找最后一個等于的元素。

1. 概述

前面說到了二分查找問題，看起來非常的簡單，的確，前面的兩種實現都不難，代碼也很容易寫，因為那只是最基礎的二分查找問題了。今天來看看幾種稍微復雜的二分查找問題：

查找第一個等于給定值的元素

查找最后一個等于給定值的元素

查找第一個大于等于給定值的元素

查找最后一個小于等于給定值的元素

1. 查找第一個等于給定值的元素

假如有一個數組 data[1,3,5,5,5,7,8,10,12] ，我們要查找第一個等于 5 的值，該怎么實現呢？如果按照普通的二分查找算法，取中間 data[4]=5，剛好等于要查找的值 5，所以程序就返回下標 4。但是很明顯不正確，因為我們要找的是第一個 5，下標為 2，那應該怎么實現呢？先來看看代碼吧：

    public static int findFirst(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) {
                if (mid == 0 || data[mid - 1] != value) return mid;
                else high = mid - 1;
            } 
            else if (data[mid] < value) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

這里的代碼和前面的普通二分查找很類似，只是在判斷 data[mid] == value 的時候，會有一些不一樣，如果 mid 等于 0，則表示這是數組的第一個元素，那么肯定就是我們要找的元素，第二種情況，如果 mid 的前一位不等于 value，那么也是我們要找的元素。

3. 查找最后一個等于給定值的元素

這種變形的二分查找和上面的這種情況很類似，還是利用上面的那個數組 data[1,3,4,5,5,5,5,10,12]，我們要查找最后一個等于 5 的元素。實現的代碼也和上面的類似：

    public static int findLast(int[] data, int value) {
        int low = 0;
        int high = data.length - 1;
        while (low <= high) {
            int mid = low + ((high - low));

            if (data[mid] == value) {
                if (mid == data.length - 1 || data[mid + 1] != value) return mid;
                else low = mid + 1;
            } 
            else if (data[mid] < value) low = mid + 1;
            else high = mid - 1;
        }
        return -1;
    }

在 data[mid] == value 的時候，會進行判斷，如果 mid 等于數組 length - 1，則說明是數組的最后一個元素，那么肯定是我們查找的，如果 mid 的前面一個元素不等于 value，則說明也是我們要查找的。邏輯跟上面說到的查找第一個等于給定值的情況相反。

4. 查找第一個大于等于給定值的元素

例如一個數組 data[1,3,5,5,5,8,8,8,10,12]，我們要查找第一個大于等于 7 的值，就是下標為 5 的值 8，應該怎么做呢？實際上實現的思路和上面的兩種問題類似，代碼其實還更簡潔：

    public static int findFirstBigger(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){
                if (mid == 0 || data[mid - 1] < value) return mid;
                else high = mid - 1;
            }
            else low = mid + 1;
        }
        return -1;
    }

當 data[mid] >= value 的時候，進行統一處理，這里有兩個判斷，一是如果 mid 等于 0，表示 mid 是數組的第一個元素，那么肯定就是我們要找的元素，第二種情況是，如果 mid 的前一個元素小于 value，那么也是我們要查找的元素。

5. 查找最后一個小于等于給定值的元素

有了對前面三種情況的理解，其實再來寫這種情況的代碼就很簡單了，直接給出代碼：

    public static int findLastSmaller(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){
                if (mid == data.length - 1 || data[mid + 1] > value) return mid;
                else low = mid + 1;
            }
            else high = mid - 1;
        }
        return -1;
    }

當然，這只是眾多二分查找變形問題中常見的幾種，可以多理解一下，自己動手實現一下。也可以拓展一些思維，例如上面的查找小于等于或者大于等于的情況，如果只是查找小于或者大于，該怎么實現呢，只需要將代碼的一些細節稍作修改即可。

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

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

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

算法練習8:二分查找-II

摘要：題目請實現有重復數字的升序數組的二分查找給定一個元素有序的升序長度為的整型數組和一個目標值，寫一個函數搜索中的第一個出現的，如果目標值存在返回下標，否則返回數據范圍進階時間復雜度，空間復雜度代碼中的類名方法名參數名已經指定題目:請實現有重復數字的升序數組的二分查找給定一個元素有序的（升序）長度為n的整型數組...

不知名網友 2021-11-26 11:10 評論0 收藏0
數據結構與算法：二分查找

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

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