Find intersection of two sorted arrays which in some cases require less than O(m+n) comparisons
algorithm, performance, python
Solution
A binary search algorithm requires `O(logm)` time to find a number in an array with length m. Therefore, if we search each number of an array with length n from an array with length m, its overall time complexity is `O(nlogm)`. If m is much greater than n, `O(nlogm)` is actually less than `O(m+n)`. Therefore, we can implement a new and better solution based on binary search in such a situation. source
However, this does not necessarily means binary search is better in than O(m+n) case. In fact, binary search approach is only better when n << m (n is very small compared to m).
Problem
Here is one way of doing this in `O(m+n)` where `m` and `n` are lengths of two arrays: ``` import random def comm_seq(arr_1, arr_2): if len(arr_1) == 0 or len(arr_2) == 0: return [] m = len(arr_1) - 1 n = len(arr_2) - 1 if arr_1[m] == arr_2[n]: return comm_seq(arr_1[:-1], arr_2[:-1]) + [arr_1[m]] elif arr_1[m] < arr_2[n]: return comm_seq(arr_1, arr_2[:-1]) elif arr_1[m] > arr_2[n]: return comm_seq(arr_1[:-1], arr_2) if __name__ == "__main__": arr_1 = [random.randrange(0,5) for _ in xrange(10)] arr_2 = [random.randrange(0,5) for _ in xrange(10)] arr_1.sort() arr_2.sort() print comm_seq(arr_1, arr_2) ``` Is there a technique that in some cases uses less than `O(m+n)` comparisons? For example: `arr_1=[1,2,2,2,2,2,2,2,2,2,2,100]` and `arr_2=[1,3,100]` (Not looking for the hash table implementation)