国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

數(shù)據(jù)結(jié)構(gòu)與算法——二分查找練習(xí)

JasinYip / 2160人閱讀

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

1. 概述

前面說(shuō)到了二分查找問(wèn)題，看起來(lái)非常的簡(jiǎn)單，的確，前面的兩種實(shí)現(xiàn)都不難，代碼也很容易寫(xiě)，因?yàn)槟侵皇亲罨A(chǔ)的二分查找問(wèn)題了。今天來(lái)看看幾種稍微復(fù)雜的二分查找問(wèn)題：

查找第一個(gè)等于給定值的元素

查找最后一個(gè)等于給定值的元素

查找第一個(gè)大于等于給定值的元素

查找最后一個(gè)小于等于給定值的元素

1. 查找第一個(gè)等于給定值的元素

假如有一個(gè)數(shù)組 data[1,3,5,5,5,7,8,10,12] ，我們要查找第一個(gè)等于 5 的值，該怎么實(shí)現(xiàn)呢？如果按照普通的二分查找算法，取中間 data[4]=5，剛好等于要查找的值 5，所以程序就返回下標(biāo) 4。但是很明顯不正確，因?yàn)槲覀円业氖堑谝粋€(gè) 5，下標(biāo)為 2，那應(yīng)該怎么實(shí)現(xiàn)呢？先來(lái)看看代碼吧：

    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 的時(shí)候，會(huì)有一些不一樣，如果 mid 等于 0，則表示這是數(shù)組的第一個(gè)元素，那么肯定就是我們要找的元素，第二種情況，如果 mid 的前一位不等于 value，那么也是我們要找的元素。

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

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

    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 的時(shí)候，會(huì)進(jìn)行判斷，如果 mid 等于數(shù)組 length - 1，則說(shuō)明是數(shù)組的最后一個(gè)元素，那么肯定是我們查找的，如果 mid 的前面一個(gè)元素不等于 value，則說(shuō)明也是我們要查找的。邏輯跟上面說(shuō)到的查找第一個(gè)等于給定值的情況相反。

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

例如一個(gè)數(shù)組 data[1,3,5,5,5,8,8,8,10,12]，我們要查找第一個(gè)大于等于 7 的值，就是下標(biāo)為 5 的值 8，應(yīng)該怎么做呢？實(shí)際上實(shí)現(xiàn)的思路和上面的兩種問(wèn)題類似，代碼其實(shí)還更簡(jiǎn)潔：

    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;
    }

當(dāng) data[mid] >= value 的時(shí)候，進(jìn)行統(tǒng)一處理，這里有兩個(gè)判斷，一是如果 mid 等于 0，表示 mid 是數(shù)組的第一個(gè)元素，那么肯定就是我們要找的元素，第二種情況是，如果 mid 的前一個(gè)元素小于 value，那么也是我們要查找的元素。

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

有了對(duì)前面三種情況的理解，其實(shí)再來(lái)寫(xiě)這種情況的代碼就很簡(jiǎn)單了，直接給出代碼：

    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;
    }

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

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/73886.html

相關(guān)文章

  • 算法練習(xí)8:二分查找-II

    摘要：題目請(qǐng)實(shí)現(xiàn)有重復(fù)數(shù)字的升序數(shù)組的二分查找給定一個(gè)元素有序的升序長(zhǎng)度為的整型數(shù)組和一個(gè)目標(biāo)值，寫(xiě)一個(gè)函數(shù)搜索中的第一個(gè)出現(xiàn)的，如果目標(biāo)值存在返回下標(biāo)，否則返回?cái)?shù)據(jù)范圍進(jìn)階時(shí)間復(fù)雜度，空間復(fù)雜度代碼中的類名方法名參數(shù)名已經(jīng)指定 題目:請(qǐng)實(shí)現(xiàn)有重復(fù)數(shù)字的升序數(shù)組的二分查找給定一個(gè) 元素有序的（升序）長(zhǎng)度為n的整型數(shù)組...

    不知名網(wǎng)友 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

    摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹(shù)關(guān)于二叉樹(shù)，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)算法常見(jiàn)練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見(jiàn)數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...

    zsirfs 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

    摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹(shù)關(guān)于二叉樹(shù)，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)算法常見(jiàn)練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見(jiàn)數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...

    you_De 評(píng)論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法：二分查找

    摘要：為檢查長(zhǎng)度為的列表，二分查找需要執(zhí)行次操作。最后需要指出的一點(diǎn)是高水平的讀者可研究一下二叉樹(shù)關(guān)于二叉樹(shù)，戳這里數(shù)據(jù)結(jié)構(gòu)與算法二叉樹(shù)算法常見(jiàn)練習(xí)在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。 常見(jiàn)數(shù)據(jù)結(jié)構(gòu) 簡(jiǎn)單數(shù)據(jù)結(jié)構(gòu)（必須理解和掌握） 有序數(shù)據(jù)結(jié)構(gòu)：棧、隊(duì)列、鏈表。有序數(shù)據(jù)結(jié)構(gòu)省空間（儲(chǔ)存空間?。?無(wú)序數(shù)據(jù)結(jié)構(gòu)：集合、字典、散列表，無(wú)序...

    gotham 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<