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