You can use Bitmap.GetPixel.  It's slow, but it may be fast enough for  
your purposes.  You wouldn't want to use it if you needed to look at each  
and every pixel, but in this case that shouldn't be necessary.

The fast way to work with Bitmap data is to use LockBits, which returns an  
IntPtr.  I'm not sure whether you need unsafe code to manipulate that or  
not, since I haven't done that sort of thing in .NET yet.

I'm not sure what the second clause in the sentence has with the first.  
That said...

"Divide and conquer" always implies multiple passes (or at least the  
potential for multiple passes...when you're lucky, the algorithm requires  
only a single pass :) ).

In this case, Ben is suggesting (I believe) that you "divide and conquer"  
relative to finding the top and bottom of the rectangle.  If the rectangle  
you're looking for does not straddle the vertical line in the middle of  
the containing rectangle, then you conceptually split the containing  
rectangle into two halves on that vertical line, and run the search again.

Keep doing this until you find a vertical line that _does_ intersect the  
rectangle you're looking for.

When you do find a vertical line that intersects the rectangle, then you  
necessarily also have found the top and bottom Y coordinates of the  
rectangle.  Using those coordinates, select a horizontal line to scan (it  
could be any line between the top and bottom, and Ben suggests simply  
using the average of the top and bottom Y coordinates), which will in a  
single pass across the containing rectangle tell you the left and right X  
coordinates of the rectangle.

Note that the "divide and conquer" part of the algorithm should be done as  
a breadth-first search.  That is, rather than completely searching one  
half, and then completely searching the other half, do the initial search  
of the middle of each half first, and only if that fails to find the  
rectangle would you do the "divide" part of the algorithm.  The reason  
being that if you do it depth-first, you have a 50/50 chance of having to  
visit literally every pixel in the half that _doesn't_ contain the  
rectangle, which is obviously counter to the whole point of doing the  
search quickly.  You might as well just start doing the vertical scans at  
the left and work your way right.

I sure hope this isn't a homework assignment.  I hate doing people's  
homework for them.  :)

Pete

One very effective way to do this is to maintain a queue (i.e. LinkedList)
of Rectangles.  Start with the whole image.  Each time you bisect the image
without hitting the target, add both halves to the queue.  Loop on the
queue.  Then you can implement one additional optimization -- bisect each
rectangle along the shorter dimension, keeping the resulting halves at less
than a 2:1 aspect ratio.