question on find value in array

Question

i have seen a few days ago such problem

there is given two array find      elements which are common   of these array

one of the solution was sort big array and then use binary search algorithm
and also there is another algorithm- brute-force algorithm

 for (int i=0;i<array1.length;i++){
  for (int j=0;j<array2.length;j++){
 if (array1[i]==array2[j]){
//code here
}
}

it's complexity is O(array1.length*array2.length); and i am interested the first method's complexity is also same yes? because we should sort array first and then use search method binary search algorithm's complexity is log_2(n) so it means that total time will be array.length*log_2(n) and about sort? please explain me which is better

Answer 1

An O(M log N) solution

Let the length of arr1 be O(M), and the length of arr2 be O(N). The sort/binary search algorithm is O(M log N).

The pseudocode is as follows:

SORT(arr2)   # N log N

FOR EACH element x OF arr1             # M
   IF binarySearch(x, arr2) is FOUND   # log N
       DECLARE DUP x

O(M log N) is vastly better than O(MN).

---

A linear-time solution

There's also a third way which is O(M+N), using a set that has a O(1) insertion and test. A hash-based set meets this expectation.

The pseudocode is as follows:

INIT arr1set AS emptySet

FOR EACH element x OF arr1    # M
   INSERT x INTO arr1set      # 1

FOR EACH element x OF arr2    # N
   IF arr1set CONTAINS x      # 1
      DECLARE DUP x

Answer 2

The first method is better. If you sort array1, the complexity of the first method is O(array1.length*log(array1.length) + array2.length*log(array1.length)), because first you sort the first array (in O(array1.length*log(array1.length))), and then for each element in the second array, you binary search it in the first array (in O(array2.length*log(array1.length)).

Answer 3

Complexity of the first solution will be:

sort_complexity(longer_array) + smaller_array.length*log_2(longer_array.length)

Answer 4

If you have an option to use an additional data structure, then using a hash would help you like this: push all elements of the first array into hash. Iterate over second array and check the presence of each element. If it is present in the hash --> it is common for both arrays.