3 ms·
> Rarely have to? For a professional programmer, writing their own binary search for actual use at work is nearly a firing offense (with a very few exceptions).
by throwaway613834 9y ago
> Rarely have to? For a professional programmer, writing their own binary search for actual use at work is nearly a firing offense (with a very few exceptions).
You really don't sound like you do much coding. I've lost count of the number of times I've had to write my own binary search simply because the existing ones were painfully inadequate.
Pretty much every standard library implementation, for example, expects the data to be in an array in memory. There's no provision for the data to be dynamically obtained (e.g. from disk or generated on the fly) or in any other form in memory (e.g. unsafe/native int pointers in C#). And have fun running your standard library's binary search, whether Python or C++ or Java or whatever, on something more abstract like the numeric interval [0.5, 1.0]. There's just no way to specify alternate termination conditions like tolerances.
Oh, and this is completely ignoring more mundane shortcomings in a significant fraction of implementations, like how in C# there is (or at least was, last I checked) no way to directly obtain both the lower and upper bounds of an equal range via binary search. At least C++ has equal_range!
I could say the same for practically any classical CS 101 algorithm like depth-first search or Dijkstra or whatever you want, too, except those don't even exist in most standard libraries in the first place... and I suspect their lack of existence is not unrelated to their likely practical inadequacy.
- aangjie 9y agoEither I've been in only mediocre to average roles(for any of the reasons, including my inability) or you're a very small minority not aware of the fact. I'd like to believe in the latter, for peace of mind, but better to believe in former for driving personal growth. hmm.
- throwaway613834 9y agoI also forgot to mention another case: where the needle you're searching for is of a different type than the items in your haystack. If you're searching for an integer in an array of strings that you know are integers... good luck convincing the type system to let you even call the binary search method, let alone figuring out which argument to the comparator is what type (if they can even be of different types).
- perl4ever 9y agoWhen I had to implement a binary search, it wasn't exactly the version you'd find in a textbook or library. I'm not sure I recall the details now, but I think it needed to return the two closest values if the search key wasn't present. And maybe there was something special about handling duplicate keys, but you get the idea. Sure, it's always good not to re-implement the wheel, but as a professional there are a million mundane reasons you get stuck doing it anyway.
- ex_amazon_sde 9y agoEx Amazon here. We started asking algorithm optimization question after realizing how important it is. You don't get to tweak binary searches every day, but if you optimize an algorithm to speed up your product by 1% only once a month and your teammates do the same the difference becomes huge year after year.
- AnimalMuppet 9y ago> You really don't sound like you do much coding. Perhaps not. I've been a professional software engineer for 32 years, though...