I Got a Knuth Check for 0x$3.00

The first typo is on page 392 of Volume 3, Sorting and Searching, eighth line from the bottom: “After an unsuccessful search it is sometime desirable to enter a new record, containing K, into the table; a method that does this is called a search-and-insertion algorithm.” Tack the desired item on to the end of the array, then start your pointer at the head of the array and do the following in a loop:

With this algorithm, things are arranged such that the item is guaranteed to be found one way or another, and the bound check only needs to be executed once when the item is found. Don’t ask me to prove it, but the Karatsuba algorithm (recursively generalized from the example above) improves the traditional method’s O(n2) multiplications to O(n(lg 3)).

Source: nickdrozd.github.io