In this paper, a binary variant of a novel nature-inspired metaheuristic algorithm called the nutcracker optimization algorithm (NOA) is presented for binary optimization problems. Because of the continuous nature of the classical NOA and the discrete nature of the binary problems, two different families of transfer functions, namely S-shaped and V-shaped, are extensively investigated for converting the classical NOA into a binary variant, namely BNOA, applicable for various binary problems. Additionally, BNOA is improved using a local search strategy based on effectively integrating some genetic operators into the BNOA’s exploitation and exploration; this additional variant is called BINOA. Both BNOA and BINOA are evaluated using three common binary optimization problems, including feature selection, 0-1 knapsack, and the Merkle–Hellman knapsack cryptosystem (MHKC), and are compared to several robust binary metaheuristic optimizers in terms of statistical information, statistical tests, and convergence speed. The experiential findings show that BINOA is better than the classical BNOA and the other rival optimizers for both the 0-1 knapsack problem and attacking MHKC and is on par with some algorithms, like the genetic algorithm for feature selection.