數(shù)據(jù)結(jié)構(gòu)與算法(七)二分法-創(chuàng)新互聯(lián)

這篇文章來講二分法，這是一種在實(shí)際情況中十分常用的算法

成都創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供正安網(wǎng)站建設(shè)、正安做網(wǎng)站、正安網(wǎng)站設(shè)計(jì)、正安網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、正安企業(yè)網(wǎng)站模板建站服務(wù)，10余年正安做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

1、思路

我們之前講過，解決計(jì)算機(jī)問題的一個(gè)常規(guī)方案就是暴力搜索，即：遍歷整個(gè)搜索空間，找到給定問題的解

在這個(gè)基礎(chǔ)上，針對(duì)問題的不同特征，我們可以應(yīng)用不同的數(shù)據(jù)結(jié)構(gòu)和算法，去優(yōu)化搜索的時(shí)間和空間效率

二分搜索算法就是針對(duì)有序區(qū)間的元素搜索問題進(jìn)行的時(shí)間效率優(yōu)化

換句話說，區(qū)間有序是應(yīng)用二分搜索算法的必要條件

如果要求在亂序數(shù)組中找到給定值，那么唯一的做法就是逐個(gè)遍歷數(shù)組元素

如果要求在有序數(shù)組中找到給定值，那么就可以使用二分搜索算法進(jìn)行處理

二分搜索算法的思路很簡單：通過比較區(qū)間中值和給定值，每次可以縮小一半搜索區(qū)間

舉個(gè)例子，給定有序數(shù)組[1, 2, 3, 4, 5, 6, 7, 8, 9]，要求找出元素6，算法步驟如下：

比較當(dāng)前區(qū)間中值5和給定值6，發(fā)現(xiàn)5< 6，所以給定值必在區(qū)間右半部分[6, 7, 8, 9]
比較當(dāng)前區(qū)間中值7和給定值6，發(fā)現(xiàn)7 >6，所以給定值比在區(qū)間左半部分[6]
比較當(dāng)前區(qū)間中值6和給定值6，發(fā)現(xiàn)6 = 6，至此就能找出給定值

2、細(xì)節(jié)

二分搜索算法的思路很簡單，但實(shí)現(xiàn)起來需要注意的細(xì)節(jié)卻有很多

下面先按上述所說思路給出一個(gè)代碼模板，該模板用于在升序數(shù)組中查找給定值

如果能夠找到，則返回對(duì)應(yīng)下標(biāo)；如果沒有找到，則返回-1

int binary_search(vector& nums, int target) {int n = nums.size();
    // 定義搜索區(qū)間為 [p1 , p2]
    int p1 = 0;
    int p2 = n - 1;
    // 定義終止條件為 (p1 >p2)
    while (p1<= p2) {// 計(jì)算中值：
        // 一般計(jì)算中值的方式是 (p1 + p2) / 2
        // 為了防止相加溢出改成 ?
        int mid = p1 + (p2 - p1) / 2;
        // 分類討論：
        // 若中值等于給定值，則表示已找到，返回結(jié)果就好
        // 若中值小于給定值，則將搜索區(qū)間約束在右半部分
        // 若中值大于給定值，則將搜索區(qū)間約束在左半部分
        if (nums[mid] == target) {// 中值等于給定值
            // 返回結(jié)果
            return mid;
        } else if (nums[mid]< target) {// 中值小于給定值
            // 更新搜索區(qū)間為右半部分，此時(shí)左邊界更新，右邊界不變
            p1 = mid + 1;
        } else if (nums[mid] >target) {// 中值大于給定值
            // 更新搜索區(qū)間為左半部分，此時(shí)右邊界更新，左邊界不變
            p2 = mid - 1;
        }
    }
    // 沒有找到，返回結(jié)果
    return -1;
}

上述的代碼思路很清晰，但實(shí)際寫起來可能會(huì)有很多細(xì)節(jié)值得注意

常見的問題集中在：搜索區(qū)間的定義、終止條件的定義、搜索區(qū)間的更新

搜索區(qū)間的定義，第4、5行
這里定義的搜索區(qū)間是左閉右閉區(qū)間[p1, p2]，初始化為p1 = 0, p2 = n - 1
當(dāng)然也有其他人定義為左閉右開區(qū)間[p1, p2)，初始化為p1 = 0, p2 = n
這兩種定義方式都是沒有問題的，區(qū)別在于后續(xù)要怎么定義終止條件和更新搜索區(qū)間
終止條件的定義，第7行
當(dāng)搜索區(qū)間為空時(shí)，就可以終止搜索，具體來說：
對(duì)于[p1, p2]，區(qū)間為空時(shí)有p1 >p2，也即while運(yùn)行條件應(yīng)為p1<= p2
對(duì)于[p1, p2)，區(qū)間為空時(shí)有p1 >= p2，也即while運(yùn)行條件應(yīng)為p1< p2
搜索區(qū)間的更新，第23、27行
判斷完中值和給定值的大小關(guān)系后，新的搜索區(qū)間應(yīng)該去掉中值分為左右兩部分，具體來說：
對(duì)于[p1, p2]，新的搜索區(qū)間應(yīng)為[p1, mid - 1]和[mid + 1, p2]
對(duì)于[p1, p2)，新的搜索區(qū)間應(yīng)為[p1, mid)和[mid + 1, p2)

3、模板

下面針對(duì)三種常見的二分搜索場(chǎng)景給出代碼模板，以后遇到相似的場(chǎng)景時(shí)可以舉一反三地解決問題

在升序數(shù)組中查找給定值唯一出現(xiàn)的位置，降序數(shù)組思路類似，可以自行推理
如果能夠找到，則返回對(duì)應(yīng)下標(biāo)；如果沒有找到，則返回-1

int binary_search(vector& nums, int target) {int n = nums.size();
    int p1 = 0;
    int p2 = n - 1;
    while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
        if (nums[mid] == target) {// 若中值等于給定值，則表示已找到，返回結(jié)果就好
            return mid;
        } else if (nums[mid]< target) {// 若中值小于給定值，則將搜索區(qū)間約束在右半部分
            p1 = mid + 1;
        } else if (nums[mid] >target) {// 若中值大于給定值，則將搜索區(qū)間約束在左半部分
            p2 = mid - 1;
        }
    }
    return -1;
}

在升序數(shù)組中查找給定值最先出現(xiàn)的位置，降序數(shù)組思路類似，可以自行推理
如果能夠找到，則返回對(duì)應(yīng)下標(biāo)；如果沒有找到，則返回-1

int lower_bound(vector& nums, int target) {int n = nums.size();
    int p1 = 0;
    int p2 = n - 1;
    while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
        if (nums[mid] == target) {// 不同之處
            // 若中值等于給定值，則將搜索范圍約束在左半部分繼續(xù)搜索
            p2 = mid - 1;
        } else if (nums[mid]< target) {// 若中值小于給定值，則將搜索區(qū)間約束在右半部分
            p1 = mid + 1;
        } else if (nums[mid] >target) {// 若中值大于給定值，則將搜索區(qū)間約束在左半部分
            p2 = mid - 1;
        }
    }
    // 不同之處
    // 最后檢查 p1 是否符合條件
    if (p1 >n - 1 || nums[p1] != target) {return -1;
    }
    return p1;
}

在升序數(shù)組中查找給定值最后出現(xiàn)的位置，降序數(shù)組思路類似，可以自行推理
如果能夠找到，則返回對(duì)應(yīng)下標(biāo)；如果沒有找到，則返回-1

int upper_bound(vector& nums, int target) {int n = nums.size();
    int p1 = 0;
    int p2 = n - 1;
    while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
        if (nums[mid] == target) {// 不同之處
            // 若中值等于給定值，則將搜索范圍約束在右半部分繼續(xù)搜索
            p1 = mid + 1;
        } else if (nums[mid]< target) {// 若中值小于給定值，則將搜索區(qū)間約束在右半部分
            p1 = mid + 1;
        } else if (nums[mid] >target) {// 若中值大于給定值，則將搜索區(qū)間約束在左半部分
            p2 = mid - 1;
        }
    }
    // 不同之處
    // 最后檢查 p2 是否符合條件
    if (p2< 0 || nums[p2] != target) {return -1;
    }
    return p2;
}

4、例題

（1）在有序數(shù)組中查找給定值可插入位置 | leetcode35

給定一個(gè)已排序數(shù)組和一個(gè)目標(biāo)值，不考慮重復(fù)元素

如果目標(biāo)值在數(shù)組內(nèi)，返回其索引，如果目標(biāo)值不在數(shù)組內(nèi)，返回其按順序插入的位置

解題思路，可轉(zhuǎn)換為在有序數(shù)組中查找第一個(gè)大于等于給定值的位置

class Solution {public:
    int searchInsert(vector& nums, int target) {int n = nums.size();
        int p1 = 0;
        int p2 = n - 1;
        while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
            if (nums[mid] == target) {p2 = mid - 1;
            } else if (nums[mid]< target) {p1 = mid + 1;
            } else if (nums[mid] >target) {p2 = mid - 1;
            }
        }
        return p1;
    }
};

（2）在有序數(shù)組中查找給定值出現(xiàn)的范圍 | leetcode34

給定一個(gè)已排序數(shù)組和一個(gè)目標(biāo)值，數(shù)組中有重復(fù)的元素

找出目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置，如果目標(biāo)值不在數(shù)組內(nèi)，則返回[-1, -1]

解題思路，可轉(zhuǎn)換為在有序數(shù)組中查找給定值最先出現(xiàn)的位置和在有序數(shù)組中查找給定值最后出現(xiàn)的位置

class Solution {public:
    vectorsearchRange(vector& nums, int target) {int p1 = lower_bound(nums, target);
        int p2 = upper_bound(nums, target);
        return (p1 == -1 || p2 == -1) ? vector{-1, -1} : vector{p1, p2};
    }

    int lower_bound(vector& nums, int target) {int n = nums.size();
        int p1 = 0;
        int p2 = n - 1;
        while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
            if (nums[mid] == target) {p2 = mid - 1;
            } else if (nums[mid]< target) {p1 = mid + 1;
            } else if (nums[mid] >target) {p2 = mid - 1;
            }
        }
        if (p1 >n - 1 || nums[p1] != target) {return -1;
        }
        return p1;
    }

    int upper_bound(vector& nums, int target) {int n = nums.size();
        int p1 = 0;
        int p2 = n - 1;
        while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
            if (nums[mid] == target) {p1 = mid + 1;
            } else if (nums[mid]< target) {p1 = mid + 1;
            } else if (nums[mid] >target) {p2 = mid - 1;
            }
        }
        if (p2< 0 || nums[p2] != target) {return -1;
        }
        return p2;
    }
};

（3）吃香蕉 | leetcode875

給定一個(gè)數(shù)組，數(shù)組中的元素piles[i]表示第i堆香蕉的數(shù)量，單位為根

返回能在給定時(shí)間h內(nèi)吃完所有香蕉的最小速度k，其中h的單位為時(shí)，k的單位為根/時(shí)

在每小時(shí)中，只能選擇一堆香蕉，如果這堆香蕉小于k根，吃完后這小時(shí)也不能吃別的香蕉

解題思路
吃香蕉的速度和能否在給定時(shí)間內(nèi)吃完所有香蕉存在單調(diào)性，可以考慮用二分查找搜索最小速度
另一個(gè)問題是給定一個(gè)速度，怎么計(jì)算需要多少時(shí)間才能吃完所有香蕉

class Solution {public:
    int minEatingSpeed(vector& piles, int h) {// 左邊界為最小速度，顯然為一
        // 右邊界為大速度，因?yàn)槊啃r(shí)最多只能吃完一堆香蕉，所以取每堆香蕉中的大根數(shù)即可
        int p1 = 1;
        int p2 = 0;
        for (int pile: piles) {p2 = max(p2, pile);
        }
        // 二分查找
        while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
            long long int tmp = getTime(piles, mid);
            if (tmp == h) {p2 = mid - 1;
            } else if (tmp< h) {p2 = mid - 1;
            } else if (tmp >h) {p1 = mid + 1;
            }
        }
        return p1;
    }

    // 給定一個(gè)速度
    // 計(jì)算需要多少時(shí)間才能吃完所有香蕉
    long long int getTime(vector& piles, int speed) {long long int time = 0;
        for (int pile: piles) {// (a + b - 1) / b 相當(dāng)于 a / b 向上取整
            time += (pile + speed - 1) / speed;
        }
        return time;
    }
};

（6）運(yùn)包裹 | leetcode1011

給定一個(gè)數(shù)組，數(shù)組中的元素weights[i]表示第i個(gè)包裹的重量，單位為噸

返回能在給定時(shí)間d內(nèi)運(yùn)走所有包裹的最小運(yùn)力c，其中d的單位為天，c的單位為噸/天

在每一天中，需要按數(shù)組順序運(yùn)走若干個(gè)包裹，要求運(yùn)走包裹的重量不能超過c噸

解題思路
運(yùn)包裹的運(yùn)力和能否在給定時(shí)間內(nèi)運(yùn)走所有貨物存在單調(diào)性，可以考慮用二分查找搜索最小運(yùn)力
另一個(gè)問題是給定一個(gè)運(yùn)力，怎么計(jì)算需要多少時(shí)間才能運(yùn)走所有包裹

class Solution {public:
    int shipWithinDays(vector& weights, int d) {// 左邊界為最小運(yùn)力，至少要等于每個(gè)包裹中的大重量
        // 右邊界為大運(yùn)力，因?yàn)榭梢砸淮芜\(yùn)走所有包裹，所以取所有包裹重量的總和
        int p1 = 0;
        int p2 = 0;
        for (int weight: weights) {p1 = max(p1, weight);
            p2 = p2 + weight;
        }
        // 二分查找
        while (p1<= p2) {int mid = p1 + (p2 - p1) / 2;
            int tmp = getTime(weights, mid);
            if (tmp == d) {p2 = mid - 1;
            } else if (tmp< d) {p2 = mid - 1;
            } else if (tmp >d) {p1 = mid + 1;
            }
        }
        return p1;
    }

    // 給定一個(gè)運(yùn)力
    // 計(jì)算需要多少時(shí)間才能運(yùn)走所有包裹
    int getTime(vector& weights, int capacity) {int curr = 0;
        int need = 1;
        for (int weight: weights) {if (curr + weight >capacity) {curr = 0;
                need = need + 1;
            }
            curr = curr + weight;
        }
        return need;
    }
};

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

新聞標(biāo)題：數(shù)據(jù)結(jié)構(gòu)與算法(七)二分法-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://muchs.cn/article4/dshcoe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站制作、Google、搜索引擎優(yōu)化、建站公司、App設(shè)計(jì)、軟件開發(fā)

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容