5 ms·

I had to write a binary search a few weeks ago in the course of Real Work. I agree technical interviews aren't the only way of assessing a candidate's qualific

I had to write a binary search a few weeks ago in the course of Real Work. I agree technical interviews aren't the only way of assessing a candidate's qualifications. Their open source projects, their writing on technical topics, and just having a geeky conversation with them are all good indicators of cluefulness. Jon Evans is clueless. No hire.

wan23 15y ago
Collections.binarySearch() ? std::binary_search() ? Not saying I don't believe you, as there are times when it does come up but IMO even if you do have to write something search-like, it's usually better to do a linear search for the sake of having more readable code.
- ericbrunstad 15y ago
  And incur a cost proportional to 1,000,000 when you could incur a cost proportional to 20? I strongly disagree.
- carussell 15y ago
  Regarding the last bit, how hard can I say "wtf"? Writing readable code and a writing a binary search are hardly at odds; they're orthogonal. Regarding the first bit, there are lots of situations where the algorithm needed is a binary search, but for which your generic search-a-sorted-array won't do. For almost any non-trivial need, really...
- Dove 15y ago
  I once needed to find several elements in a ~500,000 object array several times a second. And the criterion by which I could judge whether they were the objects I wanted was expensive to compute, and often complex -- involving looking at neighboring or seemingly unrelated objects, or the general program state. And in special cases, I needed to return a filtered slice of the array. There wasn't a library function to do what I needed, and that's a pretty serious understatement. I wrote my own libraries for the job, and still wound up writing one flavor or another of tweaked binary search about once a week.
- jallmann 15y ago
  You have no idea what I was doing (or even what language I was using), so don't presume. I benchmarked my binary search, a hand-rolled linear search, and the search function that was built into the container I was using. binary 0.019003 ms linear 3.402408 ms builtin 9.007484 ms > it's usually better to do a linear search for the sake of having more readable code For small inputs, maybe. But a binary search takes only marginally more time to test and write than a hand-rolled linear search. And anyone halfway competent should be able to recognize one when reading code. When you have more than a dozen elements or so, a linear search is simply Doing It Wrong.
- spc476 15y ago
  A project I worked on needed more than just the value (or lack of value) from a sorted array---it also needed the index where the item would have been had it been in the array. The standard binary search in the language I was using didn't return that information. Sometimes, the requirements exceed what the standard stuff gives you.

wan23 15y ago

Collections.binarySearch() ? std::binary_search() ? Not saying I don't believe you, as there are times when it does come up but IMO even if you do have to write something search-like, it's usually better to do a linear search for the sake of having more readable code.

ericbrunstad 15y ago
And incur a cost proportional to 1,000,000 when you could incur a cost proportional to 20? I strongly disagree.
carussell 15y ago
Regarding the last bit, how hard can I say "wtf"? Writing readable code and a writing a binary search are hardly at odds; they're orthogonal. Regarding the first bit, there are lots of situations where the algorithm needed is a binary search, but for which your generic search-a-sorted-array won't do. For almost any non-trivial need, really...
Dove 15y ago
I once needed to find several elements in a ~500,000 object array several times a second. And the criterion by which I could judge whether they were the objects I wanted was expensive to compute, and often complex -- involving looking at neighboring or seemingly unrelated objects, or the general program state. And in special cases, I needed to return a filtered slice of the array. There wasn't a library function to do what I needed, and that's a pretty serious understatement. I wrote my own libraries for the job, and still wound up writing one flavor or another of tweaked binary search about once a week.
jallmann 15y ago
You have no idea what I was doing (or even what language I was using), so don't presume. I benchmarked my binary search, a hand-rolled linear search, and the search function that was built into the container I was using. binary 0.019003 ms linear 3.402408 ms builtin 9.007484 ms > it's usually better to do a linear search for the sake of having more readable code For small inputs, maybe. But a binary search takes only marginally more time to test and write than a hand-rolled linear search. And anyone halfway competent should be able to recognize one when reading code. When you have more than a dozen elements or so, a linear search is simply Doing It Wrong.
spc476 15y ago
A project I worked on needed more than just the value (or lack of value) from a sorted array---it also needed the index where the item would have been had it been in the array. The standard binary search in the language I was using didn't return that information. Sometimes, the requirements exceed what the standard stuff gives you.