Skin cancer is the world’s fifth most prevalent cancer. Skin cancer is seen in one out of every three cancers. The quality of early and precise skin cancer detection is quite difficult. Some studies have been conducted on the computerized detection of malignancy in skin lesion images. The manual tuning of network architecture design is heavily reliant on domain expertise and is tough. In the present research, a one-shot neural architecture search technique is proposed that boost the search efficiency by modeling NAS as a one-shot training process of an over-parameterized supernet. As a result, various architectures can be derived from the supernet, and share the same weights. An evolutionary memetic algorithm employing local search was proposed to optimum the network architecture, which yields minimal computation time and accurate classification of benign and malignant skin lesions. Our search algorithm comprises all conceivable networks in each solution space. This approach prevents the neural architecture from being scratched. The proposed work proved efficient in ResNet search space with better outcomes than manually created networks on the ISBI dataset, which resulted in an accuracy of 93.26% and the computation cost is decreased. The search process also lasts an average of 18 h on a graphical processing unit.