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

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

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

1、思路

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

在這個基礎上，針對問題的不同特征，我們可以應用不同的數(shù)據(jù)結構和算法，去優(yōu)化搜索的時間和空間效率

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

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

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

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

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

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

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

2、細節(jié)

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

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

如果能夠找到，則返回對應下標；如果沒有找到，則返回-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) {// 計算中值：
        // 一般計算中值的方式是 (p1 + p2) / 2
        // 為了防止相加溢出改成 ?
        int mid = p1 + (p2 - p1) / 2;
        // 分類討論：
        // 若中值等于給定值，則表示已找到，返回結果就好
        // 若中值小于給定值，則將搜索區(qū)間約束在右半部分
        // 若中值大于給定值，則將搜索區(qū)間約束在左半部分
        if (nums[mid] == target) {// 中值等于給定值
            // 返回結果
            return mid;
        } else if (nums[mid]< target) {// 中值小于給定值
            // 更新搜索區(qū)間為右半部分，此時左邊界更新，右邊界不變
            p1 = mid + 1;
        } else if (nums[mid] >target) {// 中值大于給定值
            // 更新搜索區(qū)間為左半部分，此時右邊界更新，左邊界不變
            p2 = mid - 1;
        }
    }
    // 沒有找到，返回結果
    return -1;
}

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

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

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

3、模板

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

在升序數(shù)組中查找給定值唯一出現(xiàn)的位置，降序數(shù)組思路類似，可以自行推理
如果能夠找到，則返回對應下標；如果沒有找到，則返回-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) {// 若中值等于給定值，則表示已找到，返回結果就好
            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ù)組思路類似，可以自行推理
如果能夠找到，則返回對應下標；如果沒有找到，則返回-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ù)組思路類似，可以自行推理
如果能夠找到，則返回對應下標；如果沒有找到，則返回-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

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

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

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

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

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

找出目標值在數(shù)組中的開始位置和結束位置，如果目標值不在數(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

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

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

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

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

class Solution {public:
    int minEatingSpeed(vector& piles, int h) {// 左邊界為最小速度，顯然為一
        // 右邊界為大速度，因為每小時最多只能吃完一堆香蕉，所以取每堆香蕉中的大根數(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;
    }

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

（6）運包裹 | leetcode1011

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

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

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

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

class Solution {public:
    int shipWithinDays(vector& weights, int d) {// 左邊界為最小運力，至少要等于每個包裹中的大重量
        // 右邊界為大運力，因為可以一次運走所有包裹，所以取所有包裹重量的總和
        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;
    }

    // 給定一個運力
    // 計算需要多少時間才能運走所有包裹
    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)定的海外服務器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務器高可用性，企業(yè)級服務器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞標題：數(shù)據(jù)結構與算法(七)二分法-創(chuàng)新互聯(lián)
轉(zhuǎn)載注明：http://www.jbt999.com/article4/dshcoe.html

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

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

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