How to implement a BinarySearch on a custom Collection?

[Lee]

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..."

 

[Torsten Schleussner]

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

 

[Vadym Stetsyak]

Hello, Lee!

L> If a list, collection, etc is sorted than I understand that I can
L> "half" it down right? Can anyone provide an example or resource where
L> I can look?

Is it what you need?
( http://www.brpreiss.com/books/opus6/html/page452.html )

--
Regards, Vadym Stetsyak
www: http://vadmyst.blogspot.com

 

[Lee]

Vadym Stetsyak enlightened me by writing:

Hello, Lee!

Is it what you need?
( http://www.brpreiss.com/books/opus6/html/page452.html )

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..."

 

[Mike]

Vadym Stetsyak enlightened me by writing:


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 non-recursive
versions. (Tail recursion elimination may render the recursive presentation
as non-recursive 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, mid-1)
else
return binarySearch(a, value, mid+1, right)
Because the calls are tail-recursive, this can be rewritten as a loop,
making the algorithm in-place:

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 := mid-1
else
left := mid+1
return not found
hope this helps,
m

 

[Lee]

Mike enlightened me by writing:

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 non-recursive
versions. (Tail recursion elimination may render the recursive
presentation as non-recursive 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..."