In a well-implemented binary search duplicated keys are not a problem. You can even tune your code to return the first, the last, or a "random" one.
The point about the sort order matching the search order is more serious.
I've written all sorts of fundamental algorithms for embedded systems and I only really started to get good when I wrote the spec, wrote the proof, then derived the code. This was done informally, but a background in Pure Math let me do it without too much effort.
And it was worth it. Code developed that way tended to run first time with no surprises. After a while we increased the number of things we needed to prove about the code, and reliability was solid.
It seems the world of programming divides into several sub-classes, including (but not limited to):
+ Those who program web sites and databases
+ Those who program numerical systems and simulations
+ Those who program embedded devices and fundamental algorithms.
These are broad, and there are no doubt many more, but the skills required in "programming" seem to be dividing and become more differentiated.
Yeah, the duplicate key business came in because of other code hanging off the side of the search (a rather hairy algorithm that was searching for the next key with a different letter in a position -- given KLXX, increment the 2nd position until there's a key matching that criteria -- KLXX --> KMAA, or if there are no KM's, KN, KO, etc....
The point about the sort order matching the search order is more serious.
I've written all sorts of fundamental algorithms for embedded systems and I only really started to get good when I wrote the spec, wrote the proof, then derived the code. This was done informally, but a background in Pure Math let me do it without too much effort.
And it was worth it. Code developed that way tended to run first time with no surprises. After a while we increased the number of things we needed to prove about the code, and reliability was solid.
It seems the world of programming divides into several sub-classes, including (but not limited to):
+ Those who program web sites and databases
+ Those who program numerical systems and simulations
+ Those who program embedded devices and fundamental algorithms.
These are broad, and there are no doubt many more, but the skills required in "programming" seem to be dividing and become more differentiated.