Optimised library database code for sorted array of structures

Question

I have an array of structure records and function intersection and difference.

The intersection function take list1,list2,list3(an array of records),and size of both list1 and list2.

Here, intersection and difference both are the boolean operators ( like : A U B , A - B , A intersection B). Also list1 and list2 are given as input and the result is copied to list3.

My both functions are working fine. But given that the two lists are already sorted (on author name and if same author name then name of the book), how can I optimize the code? intersection is of O(n²) and difference is less than O(n²).

copy() copies a record to first argument from second argument.

//Intersection of two lists
void intersection(struct books *list1,struct books *list2,struct books *list3,int n1,int n2)
{
 int i,j,size1,size2;
 if(n1<n2){size1=n1;size2=n2;}else{size1=n2;size2=n1;}
 for(i=0;i<size1;i++)
 {
 for(j=0;j<size2;j++)
 {
 if(strcmp(list1[i].name,list2[j].name)==0 && strcmp(list1[i].author,list2[j].author)==0)
 {
 if(list1[i].copies < list2[j].copies)
 {
 copy(&list3[i],&list1[i]);
 }
 else
 {
 copy(&list3[i],&list2[j]);
 }
 }
 }
 }
}
//set difference on lists (optimised)
void difference(struct books *list1,struct books *list2,struct books *list3,int n1,int n2)
{
 int i,j,k=0,exists=0;
 for(i=0;i<n1;i++)
 {
 exists=0;
 for(j=0;j<n2 && exists==0;j++)
 {
 if(strcmp(list1[i].author,list2[j].author)==0 && strcmp(list1[i].author,list2[j].author)==0)
 {
 exists=1;
 }
 }
 if(exists==0)
 {
 copy(&list3[k],&list1[i]);
 k++;
 }
 }
}

Answer 1

Given that the two lists are already sorted, you can do MUCH better than just the naive O(|A| * |B|) implementation. Let me reduce the problem to just intersecting lists of chars, and let's say our lists are:

A: [... a elems ..., 'C', 'D', ... ]
B: [... b elems ..., 'C', 'E', ... ]

Let's say we just in the outer looped matched A's 'C' to B's 'C'. Cool, we got that right. Now, we're going to try to check for 'D'. Do we really need to start looking at B[0]? We know that B is sorted... and we know that B[b] == 'C', so we know for sure that if there is a 'D' in B then it cannot be in the first b+1 elements.

If you change your inner loop from looping over every element in the 2nd list, to just making sure you end up only walking over the list once, you can reduce your complexity to O(|A| + |B|), which is pretty huge.