High utility itemset mining has recently emerged to address the limitations of frequent itemset mining. It entails relevance measures to reflect both statistical significance and user expectations. Whether breadth-first or depth-first search algorithms are employed, most methods generate new candidates by 1-extension of existing itemsets (i.e., by adding only one item to verified itemsets to generate new potential candidates). As an alternative to 1-extension, we introduce an expansion method based on binary partition. We then define the transaction utility list and key support count and discuss a new pruning strategy. Based on the new itemset expansion method and pruning strategy, we propose an efficient high utility itemset mining algorithm called BPHUI-Mine (Binary Partition-based High Utility Itemsets Mine). Tests on publicly available datasets show that the proposed algorithm outperforms other state-of-the-art algorithms.