algorithm - question on find value in array -

I have seen such a problem a few days ago

  Find two array elements that are in these array One of the common solutions is  

one of the solutions was a large array and then uses binary search algorithms and another algorithm - brute-force algorithm other than < (For ) (int i = 0; i & lt; array1.length; i ++) {for (int j = 0; j & lt; array2.length; j ++) {if (array1 [ I] == array 2 [j]) {// code here}}

Its complexity is (array1.length array2.length); And I'm interested in the complexity of the first method, too? Because we should first sort the array and then use the search method The complexity of binary search algorithms is log_2 (n), that means the total time array will be. Length log_2 (n) and about the sort? Please explain to me which is better

a o (m log n) solution >

arr1 for length of o (m) , and length of arr2 be o (n) . Sort / binary search algorithm O (M log N) .

In this way, the pseudocode is as follows:

  sort order (arr2) # n For every element log in the binary search via AR1 # M (X, AR2 ) Found # log n DECLARE DUP x  

O (M log n) is extremely O (MN) .

---

A linear-time solution

There is also the third way O (M + N) , using a set in which O (1) entry and testing is a hash-based set fulfills this hope.

In this way the pseudocode is as follows:

  for each element X in the form of the INIT arr1set, for each element in arr1 # M INSERT x arr1set # 1 If arr2 # N is in the arr1set, x # 1 is DECLARE DUP x