P: n/a

I have a custom collection that implements IComarer right now which
implements sorting. I've googled and it seems that built in binary
search is not available in the underlying List object.
If a list, collection, etc is sorted than I understand that I can
"half" it down right? Can anyone provide an example or resource where
I can look?
Thanks,

Warm Regards,
Lee
"Upon further investigation it appears that your software is missing
just one thing. It definitely needs more cow bell..."  
Share this Question
P: n/a

Lee wrote: I have a custom collection that implements IComarer right now which implements sorting. I've googled and it seems that built in binary search is not available in the underlying List object.
If a list, collection, etc is sorted than I understand that I can "half" it down right? Can anyone provide an example or resource where I can look?
Thanks,
You can use Reflector to take a look in System.Array.BinarySearch.
There you will find how Microsoft handles that.
Regards
Torsten  
P: n/a

Vadym Stetsyak enlightened me by writing: Hello, Lee!
Is it what you need? ( http://www.brpreiss.com/books/opus6/html/page452.html )
 Regards, Vadym Stetsyak www: http://vadmyst.blogspot.com
Thanks Vadym,
So it does need to be a recursive aglo then...
Thanks again,

Warm Regards,
Lee
"Upon further investigation it appears that your software is missing
just one thing. It definitely needs more cow bell..."  
P: n/a

"Lee" <lu*************@yahoo.com> wrote in message
news:Os***************@TK2MSFTNGP10.phx.gbl... Vadym Stetsyak enlightened me by writing:
Hello, Lee!
Is it what you need? ( http://www.brpreiss.com/books/opus6/html/page452.html )
 Regards, Vadym Stetsyak www: http://vadmyst.blogspot.com Thanks Vadym,
So it does need to be a recursive aglo then...
No  typically a binary search of linear storage does not have to be
recursive  although the max. # of recursions is of course log2(n), usually
there will be no problem with recursion depth.
Here's the Wikipedia version of both the recursive and nonrecursive
versions. (Tail recursion elimination may render the recursive presentation
as nonrecursive anyway, and it's slightly more pleasing looking...) http://en.wikipedia.org/wiki/Binary_search

The algorithm
The most common application of binary search is to find a specific value in
a sorted list. To cast this in the frame of the guessing game (see Example
below), realize that we are now guessing the index, or numbered place, of
the value in the list.
The search begins by examining the value in the center of the list; because
the values are sorted, it then knows whether the value occurs before or
after the center value, and searches through the correct half in the same
way. Here is simple pseudocode which determines the index of a given value
in a sorted list a between indices left and right:
function binarySearch(a, value, left, right)
if right < left
return not found
mid := floor((left+right)/2)
if a[mid] = value
return mid
if value < a[mid]
return binarySearch(a, value, left, mid1)
else
return binarySearch(a, value, mid+1, right)
Because the calls are tailrecursive, this can be rewritten as a loop,
making the algorithm inplace:
function binarySearch(a, value, left, right)
while left ? right
mid := floor((left+right)/2)
if a[mid] = value
return mid
if value < a[mid]
right := mid1
else
left := mid+1
return not found
hope this helps,
m Thanks again,
 Warm Regards, Lee
"Upon further investigation it appears that your software is missing just one thing. It definitely needs more cow bell..."  
P: n/a

Mike enlightened me by writing: "Lee" <lu*************@yahoo.com> wrote in message news:Os***************@TK2MSFTNGP10.phx.gbl... Vadym Stetsyak enlightened me by writing:
Hello, Lee!
Is it what you need? ( http://www.brpreiss.com/books/opus6/html/page452.html )
 Regards, Vadym Stetsyak www: http://vadmyst.blogspot.com Thanks Vadym,
So it does need to be a recursive aglo then...
No  typically a binary search of linear storage does not have to be recursive  although the max. # of recursions is of course log2(n), usually there will be no problem with recursion depth.
Here's the Wikipedia version of both the recursive and nonrecursive versions. (Tail recursion elimination may render the recursive presentation as nonrecursive anyway, and it's slightly more pleasing looking...) http://en.wikipedia.org/wiki/Binary_search 
hope this helps, m
Thanks Mike. Great article and snippet.
Helps a lot.

Warm Regards,
Lee
"Upon further investigation it appears that your software is missing
just one thing. It definitely needs more cow bell..."   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 2712
 replies: 5
 date asked: Mar 1 '06
