3 ms·

Nope and can't say it ever came up in the 20 years I've been programming for myself and others.

Dav3xor 17y ago
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.
- RiderOfGiraffes 17y ago
  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.
  - Dav3xor 17y ago
    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....
- shiro 17y ago
  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.
dockd 17y ago
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.
mahmud 17y ago
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.
- FutureNerd 17y ago
  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?
  - eru 17y ago
    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.

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.

RiderOfGiraffes 17y ago
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.
- Dav3xor 17y ago
  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....
shiro 17y ago
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.

dockd 17y ago

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.

mahmud 17y ago

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.

FutureNerd 17y ago
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?
- eru 17y ago
  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.