1 // g++ -D COMPILE_MAIN BinarySearch.cpp -o BinarySearch

2

3 #include <algorithm>

4 #include <fstream>

5 #include <iostream>

6 #include <vector>

7

8 namespace BinarySearch {

9 template <typename T>

10 long rank( T key, std::vector<T> a ) {

11 long lo = 0;

12 long hi = a.size() - 1;

13 while ( lo <= hi ) {

14 long mid = lo + ( hi - lo ) /2 ;

15 if ( a[mid] < key )

16 lo = mid + 1;

17 else if ( a[mid] > key )

18 hi = mid - 1;

19 else

20 return mid;

21 }

22 return -1;

23 }

24 };

25

26 ////////////////////////////////////////////////////////////////////////////////

27

28 #ifdef COMPILE_MAIN

29

30 int main( int argc, char **argv ) {

31 std::vector<int> whitelist;

32

33 std::fstream whitelist_file( argv[1] );

34 while ( whitelist_file.good() ) {

35 int i;

36 whitelist_file >> i;

37 whitelist.push_back(i);

38 }

39 whitelist_file.close();

40

41 std::sort( whitelist.begin(), whitelist.end() );

42

43 std::cout << "Sorted whitelist" << std::endl;

44 for ( std::vector<int>::iterator it = whitelist.begin(); it < whitelist.end(); ++it ) {

45 std::cout << *it << std::endl;

46 }

47

48 while ( ! std::cin.eof() ) {

49 int key;

50 std::cin >> key;

51 if ( BinarySearch::rank( key, whitelist ) > -1 ) {

52 std::cout << key << " is in the whitelist" << std::endl;

53 }

54 }

55

56 }

57

58 #endif