This paper presents a rapid and scalable built-in self-test (BIST) diagnosis scheme for handling BIST environments with a large number of scan chains. The problem of identifying which scan cells captured errors during the BIST session is formulated here as a search problem. A scheme for adding a small amount of additional hardware that provides the capability of performing very efficient search techniques to locate the error capturing scan cells is proposed.The scheme can accurately diagnose any number of error capturing scan cells. The error-capturing scan cells can be located in time complexity that is logarithmic in the total number of scan cells in the design using the proposed approach. The technique scales well for very large designs. The hardware overhead is logarithmic in the number of scan cells and linear in the number of scan chains.