二分查找

二分查找操作的数据集是一个有序的数据集。开始时，先找出有序集合中间的那个元素。如果此元素比要查找的元素大，就接着在较小的一个半区进行查找；反之，如果此元素比要找的元素小，就在较大的一个半区进行查找。在每个更小的数据集中重复这个查找过程，直到找到要查找的元素或者数据集不能再分割。

二分查找能应用于任何类型的数据，只要能将这些数据按照某种规则进行排序。然而，正因为它依赖于一个有序的集合，这使得它在处理那些频繁插入和删除操作的数据集时不太高效。这是因为，对于插入和操作来说，为了保证查找过程正常进行，必须保证数据集始终有序。相对于查找来说，维护一个有序数据集的代价更高。此外，元素必须存储在连续的空间中。因此，当待搜索的集合是相对静态的数据集时，此时使用二分查找是最好的选择。参考

二分查找可以采用循环或递归的方式实现，下文代码采用了两种方式进行实现，并采用了模板类，可以实现多种类型数据的查找，但要能够采用<和>运算符进行大小比较。

#pragma once
#include <vector>

using namespace std;

//用于int/double/char等类型的二分查找

template <typename T >
class CBinarySearch
{
public:
    CBinarySearch(T key, vector<T> vec){
        m_key = key;
        m_vec = vec;
    };
    ~CBinarySearch() {};

    int SearchByCycle(){
        int lo = 0, hi = m_vec.size() - 1;
        int mid = 0;
        
        while (lo <= hi)
        {
            mid = (lo + hi) / 2;
            if (m_key < m_vec[mid]) hi = mid - 1;
            else if (m_key > m_vec[mid]) lo = mid + 1;
            else return mid;
        }
        return -1;
    };
    int SearchByRecursion(){
        return InnerRecursion(m_key, 0, m_vec.size() - 1);
    };
private:
    int InnerRecursion(T key, int low, int high) {
        int mid = (low + high) / 2;

        while (low <= high)
        {
            if (key < m_vec[mid])
                return InnerRecursion(key, low, mid - 1);
            else if (key > m_vec[mid])
                return InnerRecursion(key, mid + 1, high);
            else
                return mid;
        }
        return -1;
    };
    T m_key;
    vector<T> m_vec;
};

以上为二分查找模板类的实现，一下为使用实例。

int main()
{
    //int类型示例
    vector<int> int_vec = { 1,2,3,4,5,6,7,8,9 };
    int int_key = 5;

    CBinarySearch<int>* int_bs = new CBinarySearch<int>(int_key, int_vec);
    int int_result1 = int_bs->SearchByCycle();
    int int_result2 = int_bs->SearchByRecursion();

    cout << "int_result1 = " << int_result1 << endl;
    cout << "int_result2 = " << int_result2 << endl;

    //double类型实现
    vector<double> double_vec = { 1.2,2.5,3.85,4.24,5.369,6.485,7.4785,8.1,9.3,10.45 };
    double double_key = 9.3;

    CBinarySearch<double>* double_bs = new CBinarySearch<double>(double_key, double_vec);
    int double_result1 = double_bs->SearchByCycle();
    int double_result2 = double_bs->SearchByRecursion();

    cout << "double_result1 = " << double_result1 << endl;
    cout << "double_result2 = " << double_result2 << endl;

    //char类型示例
    vector<char> char_vec = { 'a','b','c','d','e','f','g','h','i','j','k','l' };
    char char_key = 'c';

    CBinarySearch<char>* char_bs = new CBinarySearch<char>(char_key, char_vec);
    int char_result1 = char_bs->SearchByCycle();
    int char_result2 = char_bs->SearchByRecursion();

    cout << "char_result1 = " << char_result1 << endl;
    cout << "char_result2 = " << char_result2 << endl;

    return 0;
}

细节问题
对于二分查找的细节问题可以参考此篇博客。