Phase Detection Autofocus
This AF method is most prevalent in digital SLR cameras. It requires dedicated hardware (line and cross-type autofocus sensors) which can increase the overall cost of a camera. Phase detection AF still uses contrast to assess where to focus, but contrast just isn't used as iteratively or throughout the image...only at the autofocus sensors. A disadvantage with the phase detection method is that it requires pre-calibration, and can therefore always misfocus if incorrectly calibrated.
Examples of phase detection AF sensor arrays
left: higher-end digital SLR (Canon 1-series) , right: midrange digital SLR (Canon 30D/40D/etc)
Contrast Detection Autofocus
This AF method is most prevalent in compact cameras and newer SLR cameras with Live View. This is because these cameras can be made less expensive by using the sensor itself to perform autofocus, with the (relatively) cheaper processing power used to determine maximal contrast. A disadvantage to contrast AF is that it cannot gauge whether the camera lens is front or back focused-- just that it is out of focus. This is primarily why it has to be used iteratively; contrast measurements at at least two lens positions are needed to assess which direction the camera should be focusing (ie, in front or in back of where it was previously focusing). The contrast detection is generally more fail proof (if given lots of light and enough time to focus) since it not reliant on pre-calibration.
increasing contrast (better focus)
Also take a look at the tutorial on Camera Autofocus (AF) for more on this topic...