A SEARCH statement in COBOL requires the table to have an INDEX defined for the table being searched. The SEARCH verb uses the index to efficiently navigate through table elements. Without a defined index, the SEARCH operation cannot function properly as it relies on index-based table access.