探索( 線形探索/二分探索/STL利用)まとめ

#前書き
探索の勉強．

#線形探索
線形探索は，配列の先頭から各要素が目的の値と等しいかを順番に調べていくもの．

[ポイント]
・番兵を導入(探索したいモノを探索先の配列の最後尾に設置)すると定数倍に高速化可能．
これは，不等価演算が減らせ，whileループの終了が保証されているため終了条件が省略可能であるからである．

##実装
[問題はこちら]

番兵を導入してみた．

main.cpp

#include <iostream>
#include <vector>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n+1);
    FOR(i, 0, n){
        cin >> s[i];
    }
    
    int q;
    cin >> q;
    vector<int> t(q+1);
    int cnt=0;
    FOR(i, 0, q){
        cin >> t[i];
        s[n] = t[i]; //番兵
        int j=0;
        while(s[j]!=t[i]){
            j++;
        }
        if(j!=n){
            cnt++;
        }
    }
    
    cout << cnt << endl;
    
    return 0;
}

#二分探索
二分探索は，昇順(降順)に整理された配列に探索を行うとき，中心を見ていくことにより探索を行うもの．どんどん配列の範囲を半分に絞っていくため，"""高速"""．逆に，配列を先に整列し二分探索をしてしまえば良い．

[ポイント]

1. まずは配列の左端(left)と右端(right)から見ていく．mid=(left+right)/2とする．
2. 探索したいものがmidより大きければmidより右側で再び二分探索，探索したいものがmidより小さければmidより左側で再び二分探索．

を繰り返す．

##実装
[問題はこちら]

・「S の要素が昇順に整列されている」という制約を有効利用し，二分探索を適用する．

main.cpp

#include <iostream>
#include <vector>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    FOR(i, 0, n){
        cin >> s[i];
    }
    
    int q;
    cin >> q;
    vector<int> t(q);
    int cnt=0;
    FOR(i, 0, q){
        cin >> t[i];
        int left=0,right=n; //n-1ではなくnなのは右端に解がある時のため
        int mid;
        while(left<right){ //二分探索
            mid = (left+right)/2;
            if(t[i]==s[mid]){
                cnt++;
                break;
            }
            if(t[i] > s[mid]){
                left = mid+1; 
            }
            if(t[i] < s[mid]){
                right = mid;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

#STLを利用したソート方法
　かなり便利．もう全部これでええやん．
##lower_bound(upper_bound)
　*lower_bound(data.begin(),data.end(),k)は指定した値k"以上"の要素が最初に現れる要素を返し、*upper_bound(data.begin(),data.end(),k)は指定した値kより"大きい"の要素が最初に現れる要素を返す．(イテレータで返すことに注意)

入力

test.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main () {
    vector<int> data;
    
    // 0～18まで2の倍数を格納
    for(int i=0;i<10;++i) {
        data.push_back(i*2);
    }
    //{0,2,4,6,8,10,12,14,16,18}

    vector<int>::iterator it1 = lower_bound(data.begin(),data.end(),7);
    vector<int>::iterator it2 = upper_bound(data.begin(),data.end(),7);
    
    vector<int>::iterator it3 = lower_bound(data.begin(),data.end(),8);
    vector<int>::iterator it4 = upper_bound(data.begin(),data.end(),8);
    
    cout << "lower_bound(7) " << *it1 << endl;
    cout << "upper_bound(7) " << *it2 << endl;
    cout << "lower_bound(8) " << *it3 << endl;
    cout << "upper_bound(8) " << *it4 << endl;
    
    return 0;
}

出力

result.cpp

lower_bound(7) 8 //7"以上"の要素が最初に現れる要素は8
upper_bound(7) 8 //7"より大きい"要素が最初に現れる要素は8
lower_bound(8) 8 //8"以上"の要素が最初に現れる要素は8
upper_bound(8) 10 //8"より大きい"要素が最初に現れる要素は10

これを先ほどの二分探索の問題に実装する．

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    FOR(i, 0, n){
        cin >> s[i];
    }
    
    int q;
    cin >> q;
    vector<int> t(q);
    int cnt=0;
    FOR(i, 0, q){
        cin >> t[i];
        if ( *lower_bound(s.begin(), s.end(), t[i]) == t[i] ) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

##binary_search
binary_search(data.begin(),data.end(),k)は，指定した値kを二分探索で検索するSTL．
trueかfalseで返す．

これを先ほどの二分探索の問題に実装する．

main.cpp

#include <iostream>
#include <vector>
#include <algorithm>

#define FOR(i,a,b) for(int i=(a);i<(b);++i)

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> s(n);
    FOR(i, 0, n){
        cin >> s[i];
    }
    
    int q;
    cin >> q;
    vector<int> t(q);
    int cnt=0;
    FOR(i, 0, q){
        cin >> t[i];
        if (binary_search(s.begin(), s.end(), t[i])) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

#あとがき
二分探索でなんでleft=mid"+1"なのだろう，left=midでは上手くいかなかった...．
あとSTL便利すぎ．