Suppose that you have k sorted arrays, each of size n. You would like to search for single element in each of the k arrays (or its predecessor, if it doesn't exist). Obviously you can binary search each array individually, resulting in a runtime. But we might think we can do better that: after all, we're doing the same search k times, and maybe we can "reuse" the results of the first search for later searches. Here's another obvious thing we can do: for every element in the first array, let's g...