In this paper we study the problem of searching the Web with online learning algorithms. We consider that Web documents can be represented by vectors of n boolean attributes. A search engine is viewed as a learner, and a user is viewed as a teacher. We investigate the number of queries a search engine needs from the user to search for a collection of Web documents. We design several efficient learning algorithms to search for any collection of documents represented by a disjunction (or a conjunction) of relevant attributes with the help of membership queries or equivalence queries.