탐색은 크게 두 가지 일반적인 범주로 나눈다. 첫번째는 룩업 탐색(lookup search)이다. 가지고 있는 자료를 이용하여 미리 준비하고 탐색하는 과정과 연관되어 있다. 두번째는 생성 탐색(generative search)이다. 찾아야 할 자료를 찾는 과정과 연관되어 있다. 생성 탐색은 종종 동적으로 계산하고, 항상 탐색의 결과를 이용하여 생성 과정을 제어한다. 좋은 예로 직장을 구하는 과정을 생각할 수 있다. 미리 많은 준비를 하지만 실제 면접을 하는 과정에서 회사에 대한 평가가 여러 면에서 바뀌게 되고 그 과정에서 많은 것을 배울 수 있다. 그리고 어떤 고용주를 찾을지도 알아낼 수 있게 된다.

이번 장에서는 주로 룩업 탐색에 대해 다룬다. 룩업 탐색이 가장 일반적인 탐색이기때문이다. 룩업 탐색은 특정한 자료의 내부 구조와 상관없이 대부분의 자료에 적용할 수 있다. 생성 탐색 알고리즘은 자료의 특성과 계산 과정에 밀접하게 관련되어 있다.

전화번호를 찾는 과정을 생각해 보자. 대부분 전화번호부를 탐색하여 매우 빠르게 원하는 전화번호를 찾는다. 여기서 전화번호부는 찾고자 하는 사람의 전화번호를 제공한다. 이러한 방법이 원시적인 룩업 탐색이다. 하지만 잘 모르는 사람보다는 아는 사람에게 전화를 걸게 되므로 큰 전화번호부 대신에 개인적으로 사용하는 작은 전화번호부를 이용하면 단 몇 초만에 원하는 전화번호를 찾을 수 있다. 이렇게 찾는 방법이 더 빠른 룩업 탐색법이다. 만약 자주 거는 전화번호라서 외우고 있다면 전화번호부를 들기도 전에 이미 뇌에서 탐색을 마치게 된다.