Closed sahilverma0696 closed 4 days ago
@sahilverma0696 Thank you for your PR, i actually forgot that i don't have a lower_bound & upper_bound function, thank you for finding out that those were missing. I will merge it soon!
@sahilverma0696 There's one problem with your code(see my commit and run the binary_search.cc test cases). When you're performing upper_bound() for the greatest element(in that case, 100) the function should return the size of the vector and not the index of the element. Remember that the upper bound returns the first index that is greater than x. Since there's no element greater than 100, it should return v.size() and not v.size() - 1. Can you fix that yourself?(it's a minor change)
Hey @spirosmaggioros yes you were correct, I compared the functions that I implemented with std functions. I found mistakes in both of those, so I updated my code and test cases for both.
And provided the test cases compared and tested with std c++ functions.
By the way, I initially followed the convention in the bin_search
function to provide the right
as vector.size()-1
, which caused me issues, so my functions take right
as vector.size()
, I think we should update the same in bin_search
as well now, to maintain the same convention.
@sahilverma0696 you are correct about the second parameter. It should be v.size() and not v.size() - 1. If you can do it make another PR because right now im implementing the image processing algorithms(plus i got work to do :)). I actually noticed it and wanted to comment it, thanks for notifying me about it.
Everything seems to work. PR merged!
Added
Btw Question: do we really need to follow the signature of passing left and right in binary search, wanted to know reasoning behind it.
Looks like OPs reddit post did make an impact. xD