This paper presents generalization bounds for a certain class of classification algorithms. The bounds presented take advantage of the local nature of the search that these algorithms use in order to obtain bounds that are better than those that can be obtained using VC type bounds. The results are applied to well-known classification algorithms such as classification trees and the perceptron.