In 1971, Knuth gave an O(n2
)-time algorithm for the classic problem of finding an optimal binary search tree. Knuth's algorithm works only for search trees based on 3-way comparisons, while most modern computers support only 2-way comparisons (e.g., <, <=, =, >=, and >). Until this paper, the problem of finding an optimal search tree using 2-way comparisons remained open --- poly-time algorithms were known only for restricted variants. We give an O(n4
)-time algorithm for the general case. The algorithm and analysis are simpler than those for the previously solved special case.