I am trying to make the algorithm I have listed below, more efficient, as in fewer comparisons. It looks at the arrays and determines which items are duplicated in each array, currently the algorithm makes 171 comparisons, it needs to be at 40 comparisions, (N -1)k.

I know that the algorithm can be more efficient if the search is aborted as soon as it has determined that a given element is either common to all collections, or it is not.

How would I implement this change to the code below to make the algorithm more efficient?

import java.*; import java.util.Arrays; public class commonElements { private static int comparisons = 0; public static void main(String[] args) { Comparable[] col_1 = {1,2,3,4,5,6,7,8,9,10}; Comparable[] col_2 = {1,4,6,8,10,12,14,5,18,20}; Comparable[] col_3 = {1,2,3,4,5,6,7,8,9,10}; Comparable[] col_4 = {1,5,10,15,20,25,30,35,40,45}; Comparable[] col_5 = {1,11,12,13,14,15,5,10,6,9}; Comparable[][] collections = {col_1, col_2, col_3, col_4, col_5}; findCommonElements(collections); } public static int sort (Comparable[][] collections){ int query = 0; int size = 0; for (int i = 0; i < collections.length; i++) { Arrays.sort((Comparable[])collections[i]); size = ((Comparable[])collections[i]).length; if (size < ((Comparable[])collections[query]).length) { query = i; } } return query; } public static Comparable[] findCommonElements(Comparable[][] collections){ int query = sort(collections); int comp; Comparable[] queryArray = ((Comparable[])collections[query]); Comparable[] temp = ((Comparable[])collections[query]); boolean found = false; for (int x = 0; x < queryArray.length; x++) { int count = 1; for (int i = 0; i < collections.length; i++) { if (i == query) { i++; } temp = (Comparable[]) collections[i]; found = binarySearch (temp, queryArray[x]); if (found) { count+= 1; } if (!found) { break; } } if (count == collections.length){ System.out.println(queryArray[x] + " was found in all of the arrays"); } } comp = getComparisons(); System.out.println("Total comparisons performed " + comp); return null; } public static boolean binarySearch(Comparable[] collections, Comparable desiredItem){ Integer low= 0; Integer high = collections.length - 1; Integer position = -1; Integer mid = 0; boolean found = false; while (low <= high && position == -1) { mid = (low + high) / 2; comparisons++; if (collections[mid].compareTo(desiredItem) == 0) { position = mid; found = true; break; } comparisons++; if (collections[mid].compareTo(desiredItem) < 0) { low = mid +1; } comparisons++; if (collections[mid].compareTo(desiredItem) > 0) { high = mid -1; } } if (position == -1) { position = low; } return found; } public static int getComparisons(){ return comparisons; } }