HomeLog InSource


[View] [Short] [Hash] [Raw]
Now I'm thinking we can just use the "merge" method. Scan through both indexes in order. Whenever we get a pair that aren't the same, scan through the other file until we find a match.

But I think that means O(N^2) quadratic time in the worst case, because whenever a value is missing from the other file, we have to rescan that whole file to check. If there's no overlap between the two sets, we rescan each file over and over.

If we started in the middle of the bigger file, we would have to scan the entire smaller file; but then, assuming we found it, we would only have to scan half of the smaller file for each remaining entry. So a binary search approach seems like it would work.