Re: Search a list/array of objects for specified criteria?

"Oliver Sturm" <oliver@xxxxxxxxxxxx> wrote in message
news:xn0f3jru11cjl6j009@xxxxxxxxxxxxxxxxxxxxxxx
Hello Rick,

In short, you recommend using the Find method of the List<T> class.
This performs a linear search, which is basically what I'm doing now.
It's acceptable but hardly optimal. I believe that a binary search
could be more efficient, even where the distribution is uneven.

Hm... I'm not sure really - it's a mathematical exercise to prove
whether it would be more efficient under the circumstances or not.
There are two problems:

* the distribution may be seriously uneven, we (I at least) don't
have any information on that
* the decision of whether or not a date falls in a given range is not
only dependent on one distributed value, but on two different ones.

Neither of these points will effect the speed of the search in the
slightest.
Remember, we are not talking about a (possibly imbalanced) binary tree.
We are talking about using a binary search algorithm over a sorted list.
That algorithm will give you the same performance as a perfectly
balanced tree. Uneven distributions of the data will not impact the
search in the slightest.

Also remember that Rick said:
<quote>
I have a large list of objects where each object has a unique
(non-overlapping) date range. The list is sorted chronologically
</quote>

Since the date ranges do NOT overlap there is a clear sequence of data
points
obj1.Start
obj1.End
obj2.Start
obj2.End
....

So, You perform a Binary search using either Start or end (the choice is
irrelevant). This seach will go as O(logN). If you were lucky enough to
hit the date on the money, then you are done. If you did not find the
exact date (far more likely), the algorithm will return a negative
number, which is the bitwise complement of the index of the next
element. In other words, the algorithm has in effect told you which item
in the Array you need to examine (off by one is more like it). Then it
is a simple matter of seeing if your date falls within the Start and End
dates for the object in question.

Of course, unless the number of data points is substantial, the total
time would be negligable in either case.

Hope this helps
Bill




<snip>



.

Relevant Pages

  • Re: Anyone know a faster way?
    ... I can do a binary search, but I was wondering if there is a faster ... way to do this.Some of these arrays have a lot of elements and I do ... What do you know about the distribution of those floating point numbers? ... expected complexity (and the latter approach would also be logN worst ...
    (microsoft.public.vc.language)
  • Re: Anyone know a faster way?
    ... I can do a binary search, but I was wondering if there is a faster ... way to do this.Some of these arrays have a lot of elements and I do ... If you know something about the distribution of the elements, ... could do a binary search where the cut is not the bisector. ...
    (microsoft.public.vc.language)
  • Re: Optimized binary search?
    ... I've designed optimized versions of binary search several times, ... could handle a lot more than 1000 lookups a second based on the search ... like you could do this with a good hash table and a good hash computation. ... better distribution. ...
    (borland.public.delphi.language.basm)
  • Re: Snex Embarasses Himself Again; Why a binary search is not analogous to an evolutionary algorith
    ... ET AL'S NFL REPORTS ... BINARY SEARCH IS NOT ANALOGOUS TO AN EVOLUTIONARY ALGORITHM ... is not the search/optimization problem addressed by the NFL Theorems. ...
    (talk.origins)
  • Re: Cobol Linear search Vs Perfrom Until
    ... applicable COBOL standard says it's supposed to do and, like it or not, the ... ALL be in order and that it contain no duplicates, ... I do know what a "binary search" does. ... > encountered by the algorithm. ...
    (comp.lang.cobol)
Loading