Looks like the algorithm 2.1 has a flaw: after low becomes equal to high , we need to take keys[low] and vals[low] instead of midKey and vals[mid] in last "IF", in other case midKey / mid may remain not actual and the function can return nil.

I put it coded in golang there https://play.golang.org/p/hXdA0CY755

PS I like the article - I've never realized that such low level thing as L1/L2 cache are so important for query optimization!