Certainly.
[Excuse the eplanation ...]
It (not Binary Search Algorithm, but the Binomial Theorem mentioned by Holden) came into play when building the "just for kicks" command-line
Rational Calculator so that it could calculate (
n choose r) ---> nCr ... using Big Ints to handle the large-number-by-nature factorials involved in the Combinations and Permutations. The code can be compiled and it will be able to calculate very large factorials, handling far-above-normal range for "nCr" ...
... it attempts to improve '!' factorial from 20! to 170! with newly designed function
Also implements C(n, r) for "combinations"
and P(n,r) for "permutations" using this new factorial function ...
That nCr part is only a
part of the "Binomial Theorem," but it is not related to the Binary Search Algorithm as far as I know.
Anything in particular about the
Binary Search algorithm that confuses you or interests you? Did you find the code interesting implemented with some
generic modern C++?
The output helps you follow along with what the code is actually doing. The Print to std::ostream is "fun" - but the algorithm itself, for searching, is ancient. I am not ignoring your inquiry about the Binomial Theorem, but just making certain that the question itself did not add unnecessary confusion about this already tricky-to-get-a-real-grasp-of
algorithm. The way "pointers" are eliminated from a certain layer of abstraction, using the (begin(), end()] sequence of STL containers, increases the chances of the youth spending less time re-inventing the wheel, and --- I don't know --- using libraries of very useful algorithms and adaptable containers?
This exercise (7) is cool because it asks the Learner to write their own version (not to use std::binary_search --- This is a fundamental but underestimated task when and if it came to just typing the code into an editor from scratch. There are header files to be included ...
and what not ...
I've been helping a friend out with a challenging task ... tired but surprisingly healthy (for now) bones. I will check in when I get to the Other Side of this oncoming Great Tiredness.
/*--------------------------------------------------------------------------
The Binomial Theorem would be coming into play with polynomials - the squares and cubes of ... but I would prefer sticking to this code for this thread, if you don't mind.
(passive aggressive?)
Why here? I don't know why you ask about
that in
this thread that has to do with implementing a Binary Search in C++. I find it, while basic, rather elegant. I had sifted through many kinds of approaches, and I played around with generic writing to ostream methods ... (the attached file has the following). Seeing the code is a weird kind of poetry. There are parts I need gdb debugger just to fully appreciate. I take delight in small breakthroughs, since they are the foundations for anything that is sprouting in the mind ... I myself had to hunt down "The Ways" ----
/* P R O G R A M M I N G : PRINCIPLES AND PRACTICE Using C++
* Bjarne Stroustrup c. 2014
*
* Mike Hentrich 2020 January
* G E N E R I C P R O G R A M M I N G : CHAPTERS 19, 20, AND 21Chapter 21: Algorithms and Maps
*
* Exercise 7: Write a binary search function for a vector<int>
* and a list<string>. Test them and compare their similarities.
*
* The implementations are very similar with the list version requiring an
* extra 'middle' iterator being created every pass through the while loop.
* The list version also relies on std::advance to move its iterators.
*
*/
#include <iostream>
#include <stdexcept>
#include <vector>
#include <list>
#include <string>
#include <experimental/random>
#include <algorithm>
template <typename T>
std::ostream& Print(std::ostream& os, const T& container)
{
os << "{ ";
for(auto ii = container.cbegin(); ii != container.cend(); ++ii)
os << *ii << ' ';
os << '}';
return os;
}
std::ostream& operator<<(std::ostream& os, const std::vector<int>& vec)
{ return Print(os, vec); }
std::ostream& operator<<(std::ostream& os, const std::list<int>& lst)
{ return Print(os, lst); }
std::ostream& operator<<(std::ostream& os, const std::list<std::string>& lst)
{ return Print(os, lst); }
// * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
template<typename Iter, typename T>
Iter bin_vec(Iter first, Iter last, const T& val)
{
auto half = std::distance(first, last);
auto end = last;
std::cout << "\n\n*first\t*last\thalf\n";
while ( (first != last) && (half != 0) ) {
std::cout << *first << '\t' << *last << '\t' << half << '\n';
if (*first == val) return first;
half /= 2;
first[half] > val
? last = first + half
: first = first + half;
}
return end;
}
template<typename Iter, typename T>
Iter bin_lst(Iter first, Iter last, const T& val)
{
auto half = std::distance(first, last);
auto end = last;
std::cout << "\n\n*first\t*last\thalf\n";
while (first != last && half != 0) {
std::cout << *first << '\t' << *last << '\t' << half << '\n';
if (*first == val) return first;
half /= 2;
auto mid = first;
std::advance(mid, half);
*mid > val
? std::advance(last, -half)
: std::advance(first, half);
}
return end;
}
int main()
try {
// test for vector
std::vector<int> vi;
for (int i = 0; i<32; ++i)
vi.push_back(std::experimental::randint(0,99));
std::sort(vi.begin(), vi.end());
std::cout << "Vector: " << vi << '\n';
std::cout << "Enter int to find (-1 to exit): ";
int i;
while ( (std::cin >> i) && (i != -1) ) {
auto it = bin_vec(vi.begin(), vi.end(), i);
if (it != vi.end()) {
std::cout << "Found value in vector: " << *it << '\n';
}
else std::cout << i << " is NOT in vi.\n";
std::cout << "Next int: ";
}
// test for list<int>
std::list<int> li(32);
copy(vi.begin(),vi.end(),li.begin());
std::cout << "\nList: " << li << '\n';
std::cout << "Enter int to find (-1 to exit): ";
while (std::cin>>i && i != -1) {
auto it2 = bin_lst(li.begin(), li.end(), i);
if (it2 != li.end()) {
std::cout << "Found value in list: " << *it2 << '\n';
}
else std::cout << i << " is NOT in li.\n";
std::cout << "Next int: ";
}
// test for list<string>
std::list<std::string> ls {
"Schopenhauer", "Cioran", "Celine", "Artaud", "Hentrich",
"Kant", "Knuth", "Stroustrup"
};
std::cout << "\nList: " << ls << '\n';
std::string str;
std::cout << "Enter string to find (-1 to exit): ";
while (std::cin>>str && str != "-1") {
auto it3 = bin_lst(ls.begin(), ls.end(), str);
if (it3 != ls.end()) {
std::cout << "Found value in list: " << *it3 << '\n';
}
else std::cout << str << " is NOT in ls.\n";
std::cout << "Next string: ";
}
std::cout << "\n\n";
}
catch (std::exception& e) {
std::cerr << "exception: " << e.what() << 'n';
}
catch (...) {
std::cerr << "exception\n";
Home
Search
Members
Login
Register