Finding intersection of two sorted arrays

Find the intersection of two sorted arrays.

C++:
01 void intersection(int *A, int *B, int m, int n, vector<int>& C)
02 {
03     int a=0;
04     int b=0;
05     while((a<m)&&(b<n)){
06         if(A[a]==B[b]){
07             C.push_back(A[a]);
08             a++;
09             b++;
10             continue;
11         }
12         if(A[a]<B[b])
13             a++;
14         else
15             b++;
16     }
17 }
The complexity of the above algorithm is O(m+n). If n<<m, can we do better? Now, we try to come up an algorithm with complexity O(nlog(m)).
C++:
01 void intersectionBinarysearch(int *A, int *B, int m, int n, vector<int>& C)
02 {
03     int a=0;
04     int b=0;
05     while(b<n){
06         int right=m1;
07         int left=a;
08         while(left<=right){
09             int mid=(left+right)/2;
10             if(A[mid]==B[b]){
11                 C.push_back(A[mid]);
12                 a++;
13                 break;
14             }
15             if(A[mid]<B[b]){
16                 left=mid+1;
17                 a=left;
18             }
19             else
20                 right=mid1;
21         }
22         b++;
23     }
24 }
Advertisements
This entry was posted in Array and linked list, Binary search. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s