# Is there such an idiom?

Bruce Cropley brucedecoy-post at yahoo.com.au
Mon Mar 20 14:02:14 CET 2006

```Per wrote:
[snip]

> Is this correct?
> s = [1,2,3,4,5...]
> t = [4,5,6,,8,...]
> how to find whether there is/are common item(s) between two list in
> linear-time?
> how to find the number of common items between two list in linear-time?

A common technique if both lists are sorted is to iterate through both
lists in parallel, advancing the smaller iterator each time. This is
the merge algorithm that is used by a merge sort, and it is O(s+t).

For two lists, the algorithm would go something like:

while not finished:
if s_iter_val < t_iter_val:
move s_iter on
elif s_iter_val > t_iter_val:
move t_iter on
else:
include / yield the value
move both iters on

For more on the standard merge algorithm, see:
http://en.wikipedia.org/wiki/Merge_algorithm

For an intersection merge, I hacked the recursive solution from
there...

def merge(a, b):
if len(a) == 0: return []
if len(b) == 0: return []
if a[0] < b[0]:   return merge(a[1:], b)
elif a[0] > b[0]: return merge(a, b[1:])
else:             return a[0:1] + merge(a[1:], b[1:])

#-------------------------8<-------------------------
import unittest

class TestMerge(unittest.TestCase):
def test_merge(self):
self.assertEquals(merge([1,2],[]), [])
self.assertEquals(merge([],[1,2]), [])
self.assertEquals(merge([1,3,5],[2,4,6]), [])
self.assertEquals(merge([1,2,3],[3,4,5]), [3])
self.assertEquals(merge([1,2,3,5,6,7],[3,4,5,7,8]), [3,5,7])

if __name__ == "__main__":
unittest.main()

HTH,
Bruce

```