In a memory, multiple pieces of entry data sorted in ascending or descending order are stored associated with addresses. With whole addresses for storing the multiple pieces of entry data as an initial search area, the search circuit repeatedly performs a search operation for comparing entry data stored in a central address of the search area with the search data, outputting the address as a search result in the case of a match, and narrowing the search area for the next search based on a magnitude comparison result in the case of a mismatch.