二分查找及其变种

#include <thread>
#include <vector>
#include <iostream>
#include <vector>
#include <random>
#include <functional>
#include <algorithm>
#include <iterator>
#include <ctime>

using namespace std;

template <typename T>
vector<T> genArray()
{

    time_t now_time;
    now_time = time(NULL);

    std::default_random_engine generator(now_time);
    std::uniform_int_distribution<T> distribution(-100,100);

    auto dice = bind ( distribution, generator );

    vector<int> v;

    for (int &_var: vector<int>(10)) {
        int e = dice();
        v.push_back(e);
    }

    sort(v.begin(), v.end());

    return v;

}

/*----------------------------------------------------
 * 常规二分查找
 *----------------------------------------------------
*/
int bSearch(vector<int> arr, int size, int value)
{
    size_t mid;
    size_t low = 0;
    size_t high = static_cast<size_t>(size) - 1;

    while (low <= high) {
        mid = low + ((high - low) >> 1);
        if(arr[mid] < value)
        {
            low = mid + 1;
        }else if (arr[mid] > value) {
            high = mid - 1;
        }else {
            return static_cast<int>(mid);
        }
    }

    return -1;
}

/*----------------------------------------------------
 * 二分查找变体一：查找第一个值等于给定值的元素：6 7 7 8
 *----------------------------------------------------
*/
int bSearch_1(vector<int> arr, int size, int value)
{
    size_t mid;
    size_t low = 0;
    size_t high = static_cast<size_t>(size) - 1;

    while (low <= high) {
        mid = low + ((high - low) >> 1);
        if(arr[mid] < value)
        {
            low = mid + 1;
        }else if (arr[mid] > value) {
            high = mid - 1;
        }else {
            if ( (mid==0) || (arr[mid - 1] != value))
                return  static_cast<int>(mid);
            else
                high = mid - 1;
        }
    }

    return -1;
}

/*----------------------------------------------------
 * 二分查找变体二：查找最后一个值等于给定值的元素：6 7 7 8
 *----------------------------------------------------
*/
int bSearch_2(vector<int> arr, int size, int value)
{
    size_t mid;
    size_t low = 0;
    size_t high = static_cast<size_t>(size) - 1;

    while (low <= high) {
        mid = low + ((high - low) >> 1);
        if(arr[mid] < value)
        {
            low = mid + 1;
        }else if (arr[mid] > value) {
            high = mid - 1;
        }else {
            if ( (mid==0) || (arr[mid + 1] != value))
                return  static_cast<int>(mid);
            else
                low = mid + 1;
        }
    }

    return -1;
}

/*----------------------------------------------------
 * 二分查找变体三：查找第一个大于等于给定值的元素：6 7 9 19 查 8
 *----------------------------------------------------
*/
int bSearch_3(vector<int> arr, int size, int value)
{
    size_t mid;
    size_t low = 0;
    size_t high = static_cast<size_t>(size) - 1;

    while (low <= high) {
        mid = low + ((high - low) >> 1);
        if (arr[mid] >= value) {
            if ( (mid==0) || (arr[mid - 1] < value))
                return  static_cast<int>(mid);
            else
                high = mid - 1;
        }else {
                low = mid + 1;
        }
    }

    return -1;
}

/*----------------------------------------------------
 * 二分查找变体四：查找最后一个小于等于给定值的元素：6 7 9 19 查 8
 *----------------------------------------------------
*/
int bSearch_4(vector<int> arr, int size, int value)
{
    size_t mid;
    size_t low = 0;
    size_t high = static_cast<size_t>(size) - 1;
    size_t len = high;

    while (low <= high) {
        mid = low + ((high - low) >> 1);
        if (arr[mid] <= value) {
            if ( (mid==len) || (arr[mid + 1] > value))
                return  static_cast<int>(mid);
            else
                low = mid + 1;
        }else {
                high = mid - 1;
        }
    }

    return -1;
}

int main()
{
    int value;

    while (1) {
        vector<int> array = genArray<int>();
        copy(array.begin(), array.end(), ostream_iterator<int>(cout, " "));
        cout<<endl<<"search value >:";
        cin >> value;
        int pos = bSearch_3(array, static_cast<int>(array.size()), value);
        cout <<"pos:"<<pos << endl;
    }

    return 0;
}

备份地址: 【二分查找及其变种】