C++實現(xiàn)二分法的一些細節(jié)(常用場景)
二分法是在一個排好序的序列（數(shù)組，鏈表等）中，不斷收縮區(qū)間來進行目標值查找的一種算法，下面我們就來探究二分法使用的一些細節(jié)，以及常用的場景：
尋找一個數(shù)；尋找左側邊界；尋找右側邊界。
一、二分法的通用框架
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
// 條件一：中間的值與目標值相同
}
else if(nums[mid] > target){
// 條件二：中間的值大于目標值
}
else if(nums[mid] < target){
// 條件三：中間的值小于目標值
}
}
return -1;
}
首先，我們先來分析一下右邊界 right 的初始值：
- 當
right=nums.size()時，初始化的區(qū)間就變成了 \([0, right-1]\)，即 \([0,right)\)； - 當
right=nums.size()-1時，初始化的區(qū)間就變成了 \([0, right]\)。
在第一種情況下，當 nums[mid] > target 時，需要將區(qū)間向左收縮，即 right=mid。這個做法的邏輯是：既然 mid 位置處大于 target，而查找區(qū)間又是 “左閉右開”，因此當 right=mid 時，新的查找區(qū)間變成了 \([0, mid)\)，這樣才不會漏掉值。同理，當 nums[mid] < target 時，需要將區(qū)間向右收縮，即 left = mid+1，因為在 "左閉右開" 的區(qū)間下，新的查找區(qū)間變成 \([mid+1, right)\) 才不會漏掉值。當目標值不在序列中時，需要將 while 的條件寫成 while(left < right) 而不是寫成 while(left<=right)，這樣會引起數(shù)組越界。
第二種情況的分析類似，這里只給出結論：
- 當
nums[mid] > target時，需要將區(qū)間向左收縮，即right=mid-1； - 當
nums[mid] < target時，需要將區(qū)間向右收縮，即left = mid+1； - 當目標值不在序列中時，需要將
while的條件寫成while(left<=right)
二、二分法查找目標值
在序列中查找一個數(shù)，如果存在則返回數(shù)的索引，如果不存在則返回 -1 。為了方便分析，我們就只用第一種情況進行說明：
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
return mid; // 查詢到目標值，直接返回目標值的位置
}
else if(nums[mid] > target){
right = mid; // 中間的值大于目標值，向左收縮區(qū)間
}
else if(nums[mid] < target){
left = mid+1;// 中間的值小于目標值，向右收縮區(qū)間
}
}
return -1; // 當沒有找到，直接返回-1
}
三、二分法查找目標值的左右邊界
上述代碼只能從序列中查找一個目標值并返回位置，當一個序列中目標值不止一個時，我們需要找到目標值最左邊的位置和最右邊的位置，這時候二分法需要進行改寫：
// 查找目標值的左邊界
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
right = mid; // 查詢到目標值不進行返回，而是收縮區(qū)間繼續(xù)查找
}
else if(nums[mid] > target){
right = mid; // 中間的值大于目標值，向左收縮區(qū)間
}
else if(nums[mid] < target){
left = mid+1;// 中間的值小于目標值，向右收縮區(qū)間
}
}
return left;
}
根據(jù)上述代碼，可以發(fā)現(xiàn)如果查找目標值的左邊界，在滿足 nums[mid] == target 時，需要縮小搜索區(qū)間的上界 right，在區(qū)間 \([left, mid]\) 中繼續(xù)搜索，直到搜索完畢 left==right。此時 left=right=左邊界。
查找右邊界的做法與左邊界類似：
// 查找目標值的左邊界
int binarySearch(vector<int>& nums, int target){
int left=0, right=nums.size();
while(left < right)
{
int mid=(left+right)/2;
if(nums[mid] == target){
left = mid+1; // 查詢到目標值不進行返回，而是收縮區(qū)間繼續(xù)查找
}
else if(nums[mid] > target){
right = mid; // 中間的值大于目標值，向左收縮區(qū)間
}
else if(nums[mid] < target){
left = mid+1;// 中間的值小于目標值，向右收縮區(qū)間
}
}
return left-1;
}
注意這里的判斷條件改成了當 nums[mid] == target 時，left = mid+1。因為搜索的區(qū)間為 "左閉右開"，所以在尋找左邊界時可令 right=mid ，在尋找右邊界時必須另 left=mid+1，不然程序會一直停在循環(huán)里面而無法跳出循環(huán)。
到此這篇關于C++實現(xiàn)二分法詳解的文章就介紹到這了,更多相關C++實現(xiàn)二分法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要為大家詳細介紹了C語言中幾種進程間通訊的方式，文中的示例代碼講解詳細，?對我們學習或工作有一定的借鑒價值，需要的可以參考一下2022-08-08
這篇文章主要為大家詳細介紹了C語言非遞歸后序遍歷二叉樹，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10
本文主要介紹了C++ std::shared_mutex讀寫鎖的使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
future和promise的作用是在不同線程之間傳遞數(shù)據(jù)。使用指針也可以完成數(shù)據(jù)的傳遞，但是指針非常危險，因為互斥量不能阻止指針的訪問；而且指針的方式傳遞的數(shù)據(jù)是固定的，如果更改數(shù)據(jù)類型，那么還需要更改有關的接口，比較麻煩2022-11-11
今天博主來講解4道經(jīng)典的指針筆試題，很多朋友沒有深刻理解函數(shù)傳參知識都會在這些題目上出錯，下面話不多說，我們開始2021-10-10
這篇文章主要介紹了在C++中加載TorchScript模型的方法，本文通過實例代碼給大家介紹的非常詳細，具有一定的參考借鑒價值,需要的朋友可以參考下2020-02-02
由于deepstream是基于gstreamer的，所以要想在deepstream上做拓展，需要對gstreamer有一定的認識，以下主要介紹Gstreamer整體框架和Gstreamer基礎概念,需要的朋友可以參考下2022-07-07
C語言實現(xiàn)通用數(shù)據(jù)結構之通用集合(HashSet)
這篇文章主要為大家詳細介紹了C語言實現(xiàn)通用數(shù)據(jù)結構之通用集合，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
C或C++報錯:ld returned 1 exit status報錯的原因及解
這篇文章主要介紹了C或C++報錯:ld returned 1 exit status報錯的原因及解決方法,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-02-02
這篇文章主要介紹了VC實現(xiàn)批量刪除指定文件的方法,是一個比較普遍且實用的功能,需要的朋友可以參考下2014-07-07