How to integrate CAPTCHA in a search form with Views
If you go into the CAPTCHA configuration page, there should be an option to "Add CAPTCHA administration links to forms". If you enable this then visit your views page, an option should appear to add a CAPTCHA next to the exposed filter (the option may be a little mangled depending on your layout, it expands out fine when you click it). 

A heads up that this can sometimes generate some extra warnings, see how you go.