Sunday 19 March 2023

Chapter 26 // Exercise 1 - Principles & Practice Using C++

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

Chapter 26 // Exercise 1

Run your binary search algorithm from section 26.1 with the tests presented in section 26.3.2.1.

I started off writing the function and following his bullet points and it had 3 distinct sections; getting the middle and comparing, then seeing if the middle was less or more than. I then got deja vu because knew I had seen this somewhere before in the book/done it before. And so I went looking through the other chapters and sure enough, I found the info I was looking for back in Chapter 21, page 795.

This then triggered a memory of realising how a binary search is actually implemented and I went back through my posts to this one:

Here we were tasked with writing a binary search for a vector, and I was a bit shocked to see my binary search I started implementing was exactly the same as the one I did 2 years ago. I even used the same std::advance and std::distance calls to get the middle iterator. 

Thanks to these tests though, I did find a bug in my code from that exercise, in that if there is only 1 element in the container, and the value we're looking for is more than the contents of the middleElement iterator; it would go into another binary search and eventually overflow. So I checked the distance was more than 1 before doing that.

No comments:

Post a Comment