C++经典算法实现系列2

上回我们说道，牛逼的C++可以实现很多牛逼的算法。我们继续之前的记录。

Algorithm 4. 二分查找

我们将实现一个二分查找的算法。
首先必须明白，二分法查找数毕竟满足：这堆数是保存在数组中，而且这堆数必须是有序排列，也就是需要要求有一定的顺序。之所以要求实在数组中，是因为，如果存在链表中，链表的存储不是连片的，
而数组是连片的，这样数组就可以非常轻而易举的通过下标index每个元素。其实我感觉C++里面好像都是用的数组吧。直接上代码吧：

int binary_search(int a[], int low, int high, int target) {
    // binary search, search x in a
    if (low > high) {
        return -1;
    }

    int mid = (low + high) / 2;
    if (a[mid] > target) {
        return binary_search(a, low, mid - 1, target);
    }

    if (a[mid] < target) {
        return binary_search(a, mid + 1, high, target);
    }

    return mid;
}

这是比较简单的二分查找的递归实现。但是请注意，二分法其实是有要求的，那就是，查找的数组必须是升序。我感觉这样查找就没有啥意思了，要是有一个牛逼的查找算法可以在一个混乱的数组中定位一个元素那就比较牛逼了。
二分查找的局限性就发生在它的前置条件上，需要数组是有序的，然而大部分数组都是无序的，如果将数组构建成为有序数组，那么又有第二个问题，必须是数组，而数组在构建有序过程中其实是非常低效的，因为数组是连片存储，在移动和 插入过程中会有很大的开销。因此让我们接下来来实现一个二叉查找树算法。据说该算法既可以构建有序的集合又可以高效率的搜寻目标。
顺便实现一个二分查找的非递归版本，其实感觉非递归更简单一些：

#include <iostream>
#include <string>
#include <vector>
using namespace std;
int binary_search(int a[], int x, int y, int target) {

    if (x > y) {
        return -1;
    }
    int mid = 0;
    while (x <= y) {
        mid = (x + y) / 2;

        if (a[mid] > target) {
            y = mid - 1;
        } else if (a[mid] < target) {
            x = mid + 1;
        } else {
            return mid;
        }
    }
    return -1;
}

int main()  {
    int a[] = {2, 4, 5, 6, 8, 9, 12};
    int r = binary_search(a, 0, 6, 12);
    cout << r << endl;
    return 0;
}

Algorithm 5. 寻找最大的K个元素

这个问题应该被归结为top k问题，而不是排序问题。这个问题有很多种解法，其中最简单的当然是先排序，然后再选取k个最大的数，还有一种解法是，使用快速排序的思想，具体如下：

1. 随机选择一个元素X，将数组S分为两部分，一部分全部大于X，一部分全部小于X，其实这就是快速排序的第一步；
2. 如果第一部分元素个数大于K，在继续在该部分查找K，重复1，直到元素个数等于K；
3. 如果第二部分元素小于K，则在第二部分继续分开，查找剩下的K-T个元素；

这个算法简单易行，但是请注意，这个top K是无序的，时间复杂度为O(nlogK)，这里我实现一个牛逼的基于模板的实现，事实上用模板更简单易懂一些：

#include <iostream>
#include <vector>
using namespace std;
// find top k implement by STL
vector<int>::iterator find_k(vector<int>::iterator begin, vector<int>::iterator end, int k) {

    vector<int>::difference_type n = k;
    if (end - begin <= k) {
        return end;
    }

    auto left = begin;
    auto right = end - 1;

    srand(time(NULL));
    int index = (int) rand() % n;
    iter_swap(begin, begin + index);

    while (left < right) {

        // traverse right than left
        while (*right <= *left && left < right) {right--;}
        if (left < right) {iter_swap(left, right);}

        while (*left > *right && left < right) { left++; }
        if (left < right) {iter_swap(left, right);}
    }

    n = left - begin;
    if (n + 1 >= k ) {
        // if left element more than k, find from left
        // TODO: why left + 1?
        return find_k(begin, left + 1, k);
    } else {
        // if left element less than k, find the rest k- n
        return find_k(left + 1, end, k - n - 1);
    }
}
int main()
{
    vector<int> a = {3, 56, 7, 89, 34, 12, 56, 39};
    auto it_r = find_k(a.begin(), a.end(), 5);

    for (auto it = a.begin(); it < it_r; it++) {
        cout << *it << " ";
    }
    cout << endl;
    return 0;
}

当然，这个问题还有一个清晰的解法，我把它叫做最小堆方法，它的思想是：

1. 首先随机选择K个数，然后从原数组中依次拿出一个数，和这里的每一个数进行比较，如果都小于，则pass该数，如果比某个元素大，就替换掉它，直到所有元素比完为止；

大家可以看到，这个算法非常简单，只需要一步，而且时间复杂度是：O(n*K)，不仅如此，这个算法的空间复杂度也很低，只需要把K个元素装入内存即可，其他元素只需要读取。这个算法我就不写出实际实现额。相反还有一个有意思的算法，也就是二分法来实现它。
二分法之前业实现过。二分法的思路是：

1. 首先我们要知道整个数组的最大值和最小值以及数组长度，然后先从中值开始，如果mid~max个数大于K，则在mid~max继续寻找，mid变成min；
2. 如果mid~max个数小于K则在min~mid继续寻找，mid变成max，不断的缩短区间，知道max-min=1;

二分法实现的思想也很简单，但是实际上，在实际问题运用中不好用。首先我觉得你必须要知道最大值最小值有时候并不太现实。这个算法复杂度也是O(n*K).