The extended adaptive multi-rate-wideband (AMR-WB+) is a standard audio codec stipulated by the 3rd Generation Partnership Project (3GPP). It has been experimentally validated by 3GPP that an AMR-WB+ audio codec well outperforms others when encoding speech or audio signals at bitrates below 24 kbps, but at the cost of high computational load, particularly when performing the vector quantization (VQ) of immittance spectral frequency (ISF) coefficients. For this sake, by no means can an AMR-WB+ audio codec implemented on mobile devices meet the energy efficiency requirement. As a solution to this problem, in this paper, we present two high-efficiency triangular inequality elimination (TIE)-based algorithms for VQ codebook search. The first is referred to as the iterative TIE (ITIE) search algorithm, and the other is substantially the combined use of ITIE and the equal-average nearest neighbor search (ENNS) algorithm, both of which are subsequently applied to quantize the vectors of ISF coefficients. Most of the codewords are ruled out herein as the candidates using one-level and two-level rejection criteria, leading to a significantly reduced number of codeword searches but still maintaining the same coding quality. With a full search algorithm as a benchmark, this work shows a reduction in the total number of operations of more than 75.21%, a figure far beyond 60.23% using the TIE algorithm with a dynamic and an intersection mechanism (DI-TIE), 60.85% using ENNS, and 64.88% using the equal-average equal-variance equal-norm nearest neighbor search (EEENNS) algorithm. Moreover, this work can be implemented on handheld devices equipped with multiple sensing components, e.g., smartphones, to provide various multimedia and audio applications, and the energy saving requirement can be achieved as well.