Chapter 21 // Exercise 7 - Principles & Practice Using C++

In this exercise I am using Visual Studio 2019 and a modified version of the std_lib_facilities header found here.

Chapter 21 // Exercise 7

Write a binary search function for a vector<int> (without using the standard one). You can choose any interface you like. Test it. How confident are you that your binary search function is correct? Now write a binary search function for a list<string>. Test it. How much do the two binary search functions resemble each other? How much do you think they would have resembled each other if you had not known about the STL?

Github: https://github.com/l-paz91/principles-practice/blob/master/Chapter%2021/Exercise%207

This one scared me at first. I think any phrase containing "binary search" scares me. Fortunately, Bjarne explains what a binary search is on pg795 and follows up with an example. I found it interesting that even a container with 10 elements can be searched faster using a binary search than just starting from the beginning.

A binary search basically reminded me of an exercise waaay back in chapter 4 (ex 4) where you had to make a "number guessing game" between 1 and 100 where the program could always guess your number in 7 answers or less due to starting in the middle then adding/subtracting half again until it got to the number.

So, he mentions binary searches expect your container to be sorted and he makes you use a vector and a list. Finding the middle is trivial for both containers however getting an iterator to the middle of a list is trickier than a vector because a list doesn't have random access iterators so you can't do list[middle]. You need to advance to the middle making the "generic" search inefficient for vectors.

I created 3 functions; ones catered specifically for vector and list and then a generic one. They're all pretty similar as I decided to use std::find() to search the containers. If we had to do this exercise much earlier in the book I think they would be extremely hardcoded without much thought to making them generic.

After this exercise I had a look at std::binary_search and was most annoyed with myself because it's 2 lines and uses std::lower_bounds(). My solutions are quite inefficient however they got the job with sorted containers (unsorted can cause problems). I made the generic one recursive as well to help with very large containers.