News for hackers. Stuff that matters.
Re:Are you one of the 10% of programmers who can write a bin... by njharman on Monday April 19, 2010 @03:39PM (#1277630)
Nope and can't say it ever came up in the 20 years I've been programming for myself and others.
Re:Are you one of the 10% of programmers who can write a bin... by Dav3xor on Monday April 19, 2010 @03:49PM (#1277653)
I've written one. It was for an embedded system.

A good, well tested binary search is a pain in the ass to write...

1. Your sorted array MUST use exactly the same ordering as the search is expecting. We built and sorted the array on a PC, and ran the search on the device, so this was not guaranteed.

2. There can be NO DUPLICATE KEYS.. Duplicate keys will eventually send the search down a blind alley and off into hyperspace. Also devilishly difficult to find if the array has a lot of items, and you don't know what the problem is.

3. The above 2 problems can sneak in during production with new data.

Re:Are you one of the 10% of programmers who can write a bin... by RiderOfGiraffes on Monday April 19, 2010 @03:55PM (#1277664)
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.

Re:Are you one of the 10% of programmers who can write a bin... by Dav3xor on Monday April 19, 2010 @04:06PM (#1277692)
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....
Re:Are you one of the 10% of programmers who can write a bin... by shiro on Tuesday April 20, 2010 @12:58AM (#1278677)
Yeah, I was just bitten the sort order one a few days ago; the key was 12octet-long unsigned integer, I combined 64bit comparison + 32bit comparison, and gotten the endian mixed up.

I used the same compare function to generate the sorted table, and also testing. So everything seemed to work fine in my unit, but once I took externally generated data...

My unit also involves b+tree and somewhat complicated merge sorting, so I first suspected they were broken and wasted several hours hunting down the wrong path. Indeed this article is good to remind me that I'm in 90% of folks.

Re:Are you one of the 10% of programmers who can write a bin... by dockd on Monday April 19, 2010 @07:16PM (#1278139)
I just did this recently to work around a bug (enhancement?) in a vendor's API.

By some coincidence, I'd looked at "Programming Pearls" and tried this exercise and got it wrong. My mistake was moving the left/right (beginning/end, whatever) to one more/less than the target location. At least I have plenty of company.

Re:Are you one of the 10% of programmers who can write a bin... by mahmud on Monday April 19, 2010 @10:20PM (#1278418)
That's because you're taught recursion is bad/difficult, and you're probably operating at the bucket and pointer level of abstraction.

Binary search, and more specifically recursion over lists and trees, and the logical reasoning over with induction is one of the most primitive skills one acquires while learning Lisp.

Re:Are you one of the 10% of programmers who can write a bin... by FutureNerd on Monday April 19, 2010 @11:40PM (#1278564)
I have to say that the usual way of writing binary search recursively doesn't help break the problem down. It's already as broken down as it gets, and you're just tweaking the single case. The loop version wins for clarity.

I think second runner-up is the recursive version where you use slices... does lisp have slices?

Re:Are you one of the 10% of programmers who can write a bin... by eru on Tuesday April 20, 2010 @04:27PM (#1280493)
Loops are just special cases of recursion.

And binary search is definitely not the right operation on linked lists. So even in Lisp you should use a different data structure if you want to do a binary search.