algorithm to compare a sorted array

(4.) - instead of binary search do a linear search.

Overall complexity: O(n) - as you visit every item exactly once.

Totally untested (and doesnt work well when there are duplicates):

var same = new List<int>();
var inAonly = new List<int>();
var inBonly = new List<int>();

int b = 0;
int a = 0;
//first look at all the elements until one of the lists run out of elements
for(; a < inputa.Count && b < inputb.Count;) {
     //if element is the same, then add to same
     //and the problem with duplicates is found here, if a contains two "1", but b only contains one, then same will report a single "1", but inAonly will also contain a "1"
     if (inputa[a] == inputb[b]){
       same.Add(inputa[a]);
       a++;
       b++;
     }
     //otherwise, we check if a < b, if that is the case, we know that a only exists in a, otherwise it must only exist in b.
     else if (inputa[a] < inputb[b])
     {
        inAonly.Add(inputa[a]);
        a++
     } else         {
        inBonly.Add(inputb[b]);
        b++
     }
}
//add the rest of the elements if one array is longer than the other
for(; a < inputa.Count;a++)
   inAonly.Add(inputa[a]);
for(; b < inputb.Count;b++)
   inBonly.Add(inputb[b]);

As both array`s are sorted. Best is to use a linear search.

If the arrays were blocks of memory - something that you might have allocated with malloc, you can speed up the compares by casting the array to 32 or 64 bit integers. That way you'd be able to compare a number of array elements with a single == test.

Also if you kow the array has a specific number of elements then unrolling the loop to, say, 8 if statements will be faster. It will save the compare and jump at the end of each run through the loop.

@Alvin Your algorithm seems to be right for me. As you have to point out similarities and differences you will have to do search in case of every difference.

I think that complexity will be better than nlgn, as you dont have to search in the complete array on every difference. This is because you are discarding the elements till pos as well.

If array1 and array2 have the same size then iterate over them and compare them element by element. When first difference is found => the arrays are different. If you reach the end of the arrays it means they are equal. The complexity is O(array's length) in time and O(1) in memory.

If array1 and array2 have different size then allocate another array with size - the range of the elements, and initialize it with zeros ( array3 ). For every element in array1 increment element in array3 like this: array3[array1[i]]++

After that iterate the same way array2, but decrement: array3[array2[i]]--

After that for every element in array3 you have 3 possibilities:

• if array3[i] == 1 //then element i is in array1 but not in array2
• if array3[i] == -1 //then element i is in array2 but not in array1
• if array3[i] ==0 //then element i is in both arrays or in none of them.

Time complexity - O(range), memory complexity - O(range). If the range does not start from 0, then you can make an offset for every index.

Example:

• range: 1-15
• array1: 1 2 4 5 8 9 12
• array2: 1 4 8 10 12 13 14

After step1 array3 will look like this:

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

value: 1 1 0 1 1 0 0 1 1  0  0  1  0  0  0

After step2 array3 will look like this:

index: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

value: 0 1 0 0 1 0 0 0 1 -1  0  0 -1 -1  0

You are on the correct track with how you approach this, however the search isn't necessary. (see bottom for actual algorithm)

start with 2 pointers pointing to the beginning:

        v
array1: 1 2 4 5 8 9 12

        v
array2: 1 4 8 10 12 13 14

(just as you have) if the elements are the same add them to you "In-Both" set then increment both pointers so now we have:

          v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

So now we come across differing elements, instead of searching here we can take advantage of the fact that we know for a fact there can not be a 2 past where the pointer is in array2 so we add 2 to our "Only_in_array1" set. and increment only the array1 pointer. so we end up with:

            v
array1: 1 2 4 5 8 9 12

          v
array2: 1 4 8 10 12 13 14

We end up with matching so we add 4 to the "In-Both" and increment both pointers:

              v
array1: 1 2 4 5 8 9 12

            v
array2: 1 4 8 10 12 13 14

If you continue this pattern you'll eventually end up with:

                     v
array1: 1 2 4 5 8 9 12

                  v
array2: 1 4 8 10 12 13 14

and when the first pointer falls off the array you'll know the rest of the elements in the second (longer) array aren't in the first.

To Generalize the algorithm:

• Start with 2 pointers at the start of both arrays (and initialize and datastructures you'll want to hold information: I used 3 lists/sets)

• You can now have one of three cases

  1. value of p1 is equal to p2: Add the value to your in both array and increment both

  2. value of p1 is less than p2: Add the value of p1 to your only in array1 array and increment only p1

  3. value of p1 is greater than p2: Add the value of p2 to your only in array2 array and increment only p2

• Loop on those conditions until you reach the end of one (or both if it happens that way) of your arrays. Then add any remaining items in the other list to it's respective only in arrayX list.

This algorithm only hits each item once so it should be O(n). Hope this helps