I think there are two approaches. One is to just write the code from the description. This probably produces lots of errors. Also probably most popular choice if you tell someone turn this description into code.
Other approach is to think a bit about invariants, put the necessary checks in, modify state with conditions in mind. I think this is more likely to produce correct code. I’d also say most (or at least many) developers can do this with the proper hint.
I’m not sure what this says about the state of software development. In school everyone is taught the basic techniques of outlining and structuring an essay, but ask somebody to write something and they’ll probably just wing it. I didn’t outline this comment either.
That is what Back is teaching his students with good results in his Invariant-Based Programming (pdf slides).
Note: This is also the first use of my Raspberry Pi 3. Just seemed fitting to make Lobsters first thing it sees. :)
I’ve always implemented it by falling back to a linear search after the gap gets small enough. Yes it’s cheating but also easier to get right :)
So the author rediscovers C++ lower_bound except he gets it wrong in the end by returning the position only when the value is found instead of in all cases. Why does everyone implement binary search function to return -1 if it isn’t found? That’s just bad interface design.
If there is something C++ got right, it’s the use of half-open ranges and the STL.
In the 90% - got < reversed.
Don’t like the invariants approach. The key is the observation that if (p,n) is a pointer to an n element sequence
then, in pseudo C, if n>2, (p,n) = (p,n/2) concat (p+n/2,1) concat (p+n/2+1, n/2 -1 )
if n <3 then special case it.