Mercurial > Algorithms__Sedgewick
view algs4-c++/BinarySearch/BinarySearch.cpp @ 1:5cc971338a2b
Updated BinarySearch.cpp to work in either c++99 or c++11 modes.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Sat, 16 May 2015 17:42:16 -0500 |
| parents | 17ee997bf124 |
| children |
line source
1 // g++ -std=c++11 -D BINARY_SEARCH_MAIN BinarySearch.cpp -o BinarySearch
3 #include <algorithm>
4 #include <fstream>
5 #include <iostream>
6 #include <vector>
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 };
26 ////////////////////////////////////////////////////////////////////////////////
28 #ifdef BINARY_SEARCH_MAIN
30 int main( int argc, char **argv ) {
31 std::vector<int> whitelist;
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();
41 std::sort( whitelist.begin(), whitelist.end() );
43 std::cout << "Sorted whitelist" << std::endl;
44 #if __cplusplus >= 201103
45 for ( auto it = whitelist.begin(); it < whitelist.end(); ++it ) {
46 #else
47 for ( std::vector<int>::iterator it = whitelist.begin(); it < whitelist.end(); ++it ) {
48 #endif
49 std::cout << *it << std::endl;
50 }
52 while ( ! std::cin.eof() ) {
53 int key;
54 std::cin >> key;
55 if ( BinarySearch::rank( key, whitelist ) > -1 ) {
56 std::cout << key << " is in the whitelist" << std::endl;
57 }
58 }
60 }
62 #endif