[C++知识库]C++二分常用算法和排列算法

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;
/*
* binary_search：查找某个元素是否出现。
* lower_bound：查找第一个大于或等于某个元素的位置。
* upper_bound：查找第一个大于某个元素的位置。
* equal_range：查找某个元素出现的起止位置。注意，终止位置为最后一次出现的位置加一。
*/

// 查找第一个大于或等于某个元素的位置
void LowerBound()
{
    vector<int> v;
    vector<int>::iterator iter;
    for (int i = 1; i <= 20; i++) {
        v.push_back(i);
    }
    sort(v.begin(), v.end());
    cout << "array: ";
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    /*  lower_bound */
    cout << "lower_bound function, value = 3: " << endl;
    int pos = lower_bound(v.begin(), v.end(), 3) - v.begin();

    cout << "value >= 3 pos: " << pos << " the value = " << *lower_bound(v.begin(), v.end(), 3) << endl;
    cout << endl;
}

// 查找第一个大于某个元素的位置
void UpperBound()
{
    vector<int> v;

    for (int i = 1; i <= 20; i++) {
        v.push_back(i);
    }
    sort(v.begin(), v.end());
    cout << "array: ";
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    /*  upper_bound */
    cout << "upper_bound function, value = 3: " << endl;
    int pos = upper_bound(v.begin(), v.end(), 3) - v.begin();
    cout << "value >3 pos: " << pos << " the value = " << *upper_bound(v.begin(), v.end(), 3) << endl;
    cout << endl;
}

// 二分查找某个元素是否出现
void BinarySearch()
{
    vector<int> v;
    for (int i = 1; i <= 20; i++) {
        v.push_back(i);
    }
    sort(v.begin(), v.end());
    cout << "array: ";
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    /*  binary_search */
    cout << "binary_search function value = 3: " << endl;
    cout << "3 is " << (binary_search(v.begin(), v.end(), 3) ? "" : "not ") << " in array" << endl;

    /*  binary_search */
    cout << "binary_search function value = 6: " << endl;
    cout << "6 is " << (binary_search(v.begin(), v.end(), 6) ? "" : "not ") << " in array" << endl;
    cout << endl;
}

bool Greater(int i, int j)
{
    return (i > j);
}

// 查找某个元素出现的起止位置
void EqualRange()
{
    int ints[] = { 10,20,30,30,20,10,10,20 };
    vector<int> v(ints, ints + 8);                         // 10 20 30 30 20 10 10 20
    pair<vector<int>::iterator, vector<int>::iterator> bounds;

    cout << "array: ";
    copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
    cout << endl;

    // using default comparison:
    sort(v.begin(), v.end());                              // 10 10 10 20 20 20 30 30
    bounds = equal_range(v.begin(), v.end(), 20);            //          ^        ^
    cout << "equal_range function, value = 20: " << endl;
    cout << "bounds at positions " << (bounds.first - v.begin());
    cout << " and " << (bounds.second - v.begin()) << endl;

    // using "Greater" as comp:
    sort(v.begin(), v.end(), Greater);                   // 30 30 20 20 20 10 10 10
    bounds = equal_range(v.begin(), v.end(), 20, Greater); //       ^        ^
    cout << "equal_range function, value = 20: " << endl;
    cout << "bounds at positions " << (bounds.first - v.begin());
    cout << " and " << (bounds.second - v.begin()) << endl;
    cout << endl;
}


// 当前排列的前一个排列
void PrevPermutation()
{
    vector<int> num(3, 0);
    num = { 1,2,3 };
    cout << "prev_permutation function, value = [1, 2, 3]: " << endl;
    do {
        cout << num[0] << " " << num[1] << " " << num[2] << endl;
    } while (prev_permutation(num.begin(), num.end()));
    cout << endl;
}

// 当前排列的下一个排列
void NextPermutation()
{
    vector<int> num(3, 0);
    num = { 1,2,3 };
    cout << "next_permutation function, value = [1, 2, 3]: " << endl;
    do {
        cout << num[0] << " " << num[1] << " " << num[2] << endl;
    } while (next_permutation(num.begin(), num.end()));
    cout << endl;
}

int main(int argc, char** argv)
{
    LowerBound();
    UpperBound();
    BinarySearch();
    EqualRange();
    PrevPermutation();
    NextPermutation();
    return 0;
}