进阶版入口 递归版算法(deep变量是为了测试,实际生产可不需要): 核心算法:
#include <iostream> #include <vector> #include <fstream> #include <iterator> #include <algorithm> #include <string> using namespace std; template<typename T,typename Container> int Rank(const T& key, const Container& c, const int& lo,const int& hi,int& deep) { if (lo > hi) return -1; int mid = lo + (hi - lo) / 2; //use to test cout << "deep: " << deep << ends << "lo : " << lo << ends << "hi : " << hi << endl; if (key > c[mid]) { ++deep; return Rank(key, c, mid + 1, hi,deep); } else if (key < c[mid]) { ++deep; return Rank(key, c, lo, mid - 1,deep); } else return mid; } template<typename T,typename Container> int BinarySearch(const T& key,Container& c) { //deep表示 递归深度 int deep = 0; //必须要排序 可以把这步放在调用BinarySearch()之前避免对一个序列 //重复调用sort(); sort(begin(c), end(c)); return Rank(key, c, 0, static_cast<int>(end(c)-begin(c))-1,deep); }测试专用代码:
void test(const string& mode, const string& file) { ifstream in(file); vector<int> c; copy(istream_iterator<int>(in), istream_iterator<int>(), back_inserter(c)); auto f = [=,&c](const int& key) { //从标准输入找出文件中存在的 if (mode == "exist") { if (BinarySearch(key, c) != -1) { cout << "the key: " << key << "is exist in" << file << endl; } } if (mode == "noexist") { if (BinarySearch(key, c) == -1) { cout << "the key: " << key << "is not exist in" << file << endl; } } }; for_each(istream_iterator<int>(cin), istream_iterator<int>(),f); }main.cpp
int main() { test("exist", "test.txt"); system("pause"); return 0; }非递归算法：
#include <iostream> #include <vector> #include <fstream> #include <iterator> #include <algorithm> #include <string> using namespace std; template<typename T,typename Container> int BinarySearch(const T& key, Container& c) { sort(begin(c), end(c)); int lo = 0; int hi = static_cast<int>(end(c) - begin(c))-1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (c[mid] > key) hi = mid - 1; else if (c[mid] < key) lo = mid + 1; else return mid; } return -1; }测试代码:
void test(const string& mode, const string& file) { ifstream in(file); vector<int> c; copy(istream_iterator<int>(in), istream_iterator<int>(), back_inserter(c)); auto f = [=,&c](const int& key) { //从标准输入找出文件中存在的 if (mode == "exist") { if (BinarySearch(key, c) != -1) { cout << "the key: " << key << " is exist in" << file << endl; } } if (mode == "noexist") { if (BinarySearch(key, c) == -1) { cout << "the key: " << key << "is not exist in" << file << endl; } } }; for_each(istream_iterator<int>(cin), istream_iterator<int>(),f); }main.cpp
int main() { test("exist", "test.txt"); system("pause"); return 0; }