Biclustering algorithms are very effective tools for processing gene expression datasets. Biclustering methods can be divided into two main categories, which are binary biclustering and non-binary biclustering. A binary matrix is usually converted from pre-processed gene expression data, which can effectively reduce the interference from noise and abnormal data, and is then processed using a binary biclustering algorithm. In this paper, we propose a new binary biclustering algorithm to deal with binary matrices, called the Adjacency Difference Matrix Binary Biclustering algorithm (AMBB) to address the drawback that most binary biclustering algorithms could not efficiently handle large gene expression data. AMBB constructs the adjacency matrix based on the adjacency difference values, and the output clusters are submatrices obtained by continuously updating the adjacency matrix that is constructed from the adjacency differences matrix. The adjacency matrix allows for clustering of genes that undergo similar reactions under different conditions into clusters, which is important for subsequent genes analysis. Meanwhile, experiments on synthetic and real datasets visually demonstrate that the AMBB algorithm has high practicability.