On Wed, 04 Mar 2009 13:55:10 -0800, Andrei Alexandrescu wrote: > bearophile wrote: >> Andrei Alexandrescu: >>> Binary search is rather common. >> >> Oh, yes, sorry, I meant among the ones you have listed there... > > Of five, three are frequent (linear, binary, Boyer-Moore), one is a form > of set intersection (find sorted in sorted), and the odd one is: > > find(a, assumeSorted(b)); > > This is rare but has excellent best-case complexity (is it O(a.length / > b.length)?) and is easy to add for completeness. > >>> As an aside, your use of "index" suggests you return integrals out of >>> the function. IMHO that's strongly unrecommended. >> >> I don't want to use too much of your time (that it may be better spent >> with your new child), but I don't understand what you mean. That >> index() function is meant the index position of the item or >> sub-sequence into the bigger array (or iterable), and it returns -1 if >> not found. This is an usual design. > > This is an extremely sloppy design. That it is usual doesn't make things > any better! > >> Some people think that such controls for -1 value aren't always done, >> so to avoid that and some bugs, it's better to raise something like >> IndexException when the needle isn't found. > > Yah, this is the subject of a long rant but in short: returning int from > find means that essentially that find is unusable with anything except > random access structures. This in turn means you'd have to have > different means, APIs, and user code to deal with e.g. lists, in spite > of the fact that linear search is the same boring thing for all: look at > the current thing, yes/no, move on to the next thing. IMHO ever since > the STL has seen the light of day there is no excuse, not even sheer > ignorance, to ever traffic in integers as a mean to access elements in > containers, in any language that has even the most modest parameterized > types capability. > > Returning int from find is an insult. To add injury to it, have find > also return an int for a list. > > "Is this item in this list?" > "Yeppers. It's the 538th element. Took me a hike to find it." "Well I > wanted to do something with it." "Then go get it. I'm telling you, it'll > take exactly 538 steps."
BTW, what happens if you pass a sorted list into find? Intuitively, you'd assume you can pass as assumeSorted? But you can't really do anything but linear search? Then what if you pass a tree structure into find? It's sorted, but not exactly random access... I think find should return an iterator/pointer fine, but I don't think there's a find template that can be used on all possible container types. Probably the best solution I think is to implement find inside the container itself, and have the global find function advance a range to the point of the element (or return an empty range if not found), with "quick" searches reserved for sorted random-access ranges. Note that stl works this way. -Steve
