實作

大於等於

問題定義

給定一單調上升之數列，求第一個大於等於某特定值的元素索引值並定義其為「下界」，當下界不存在則回傳數組長度。

思路

給定數組[1,2,4,5,5,6,7]，令特定值為5則應該回傳下界為3

可以看到我們能將數列分為右側都大於等於特定值和左側都小於特定值，而我們回傳之索引值正好是大於等於特定值的數列之下界。

首先，我們以閉區間之寫法來表達思路:

• 區間範圍為[left,right]，left指向索引值0，right指向索引值6
• mid為[left,right]的中間位置
• 當left>right時，區間為空

依據上述思路提出，演算法步驟:

1. 若arr[mid]>=特定值，則[mid,right]區間內所有元素均大於等於特定值，因此right左移，故right=mid-1。
2. 否則，則是[left,mid]區間內所有元素均小於特定值，因此left右移，故left=mid+1。
3. 重複上述動作直到區間被刪減為空，此時left將會停在下界，故回傳left。

程式碼

可執行下列程式碼以利思考。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
    int n,x;
    
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cin>>x;
    sort(a,a+n);
    
    int left=0,right=n-1;//[0~N-1]的閉區間 
    while(left<=right){//[left~right]大小為零結束 
        int mid=(right+left)/2;
        //cout<<left<<' '<<mid<<' '<<right<<'\n';
        if(a[mid]>=x) right=mid-1;
        else left=mid+1;
    }
    
    cout<<left<<'\n';//回傳索引值
    return 0;
} 

小於等於

問題定義

給定一單調上升之數列，求最後一個小於等於某特定值的元素索引值並定義其為「上界」。

思路

一樣給定數組 [1,2,4,5,5,6,7]，令特定值為則應該回傳上界為4

首先我們一樣能將數列分為右側都大於特定值和左側都小於等於特定值，透過觀察我們可以發現，小於等於特定值的數列上界和大於特定值下界是相鄰的所以 上界 = 下界 - 1。因此，所有找上界的问题，都可以轉換為「互補的」找下界的問题。

• 區間範圍為[left,right]，left指向索引值0，right指向索引值6
• mid為[left,right]的中間位置
• 當left>right時，區間為空
• 這次要查找的元素為大於特定值，故right判斷式要改為a[mid]>x

依據之前的思路提出相同的演算法步驟:

1. 若arr[mid]>=特定值，則[mid,right]區間內所有元素均大於等於特定值，因此right左移，故right=mid-1。
2. 否則，則是[left,mid]區間內所有元素均小於特定值，因此left右移，故left=mid+1。
3. 重複上述動作直到區間被刪減為空，此時left將會停在下界而right會停在left-1的位置即為「上界」，故回傳right。

程式碼

可執行下列程式碼以利思考。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
    int n,x;
    
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cin>>x;
    sort(a,a+n);
    
    int left=0,right=n-1;//[0~N-1]的閉區間 
    while(left<=right){//[left~right]大小為零結束 
        int mid=(right+left)/2;
        //cout<<left<<' '<<mid<<' '<<right<<'\n';
        if(a[mid]>x) right=mid-1;
        else left=mid+1;
    }
    
    cout<<right<<'\n';//回傳索引值
    return 0;
} 

總結

二分搜無論是找下界、還是找上界，都可以套用「找下界」的思路來實作：

• 首先是循環條件 若是閉區間的話以left <= right，表示區間不為空，開區間則是以left < right，表示區間不為空。

• 再來if的判定條件和問題的比較規則是相同的，比如要找满足 x >= target 的第一个元素，就令 if a[mid] >= target；要找滿足 x > target 的第一个元素，就令 if a[m] > target。

• 接著if為真時，以閉區間為例需更新 right：right = mid - 1；否則 left = mid + 1;而開區間則是更新 right：right = mid ；否則 left = mid + 1。

• 最後當循環结束時，閉區間的left會指向下界，right則指向「互補條件」的上界；而開區間的left和right則都指向下界

補充

開區間二分搜寫法

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
    int n,x;
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cin>>x;
    int left=0,right=n;//[0~N-1]的開區間 
    while(left<right){//[left~right)大小為零結束 
        int mid=(right+left)/2;
        //cout<<left<<' '<<mid<<' '<<right<<'\n';
        if(a[mid]>=x) right=mid;
        else left=mid+1;
    }
    cout<<left<<'\n';//回傳索引值
    return 0;
} 

c++二分搜函式

1. lower_bound( begin,end,num,greater() ):從陣列的begin位置到end-1位置二分查詢第一個大於或等於num的數字，找到返回該數字的地址，不存在則返回end。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
    int n,x;
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cin>>x;
    cout<<lower_bound(a,a+n,x)-a<<'\n';
    //通過返回的地址減去起始地址begin,得到索引值
    return 0;
} 

2. upper_bound( begin,end,num,greater() ):從陣列的begin位置到end-1位置二分查詢第一個大於num的數字，找到返回該數字的地址，不存在則返回end。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int a[100005];
int main(){
    int n,x;
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cin>>x;
    cout<<upper_bound(a,a+n,x)-a<<'\n';
    //通過返回的地址減去起始地址begin,得到索引值
    return 0;
} 

3. binary_search( begin,end,num,greater() ):從陣列的begin位置到end-1位置二分查詢num是否存在陣列中，找到返回True，不存在則返回False。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
int main()
{
    int n,x;
    cin>>n;
    for(int i=0;i<n;++i)cin>>a[i];
    cin>>x;
    if(binary_search(a,a+n, x)) 
        cout << "found" <<'\n';
    else 
        cout << "not found" <<'\n';
  return 0;
}