Checking 2 arrays - algorithm

[reQuorter]

Hello,

I've wrote an algorithm to check 2 arrays (A & 😎, if there is same element in both of them, this element goes to 3rd array (C).
I know there is PHP function like array_intersect, but I've to write algorithm.

My code:

<?php

$A = Array('Joe', 'Bob', 'Sarah', 'Bill', 'Suzy');
$B = Array('Joe', 'pos', 'suzy', 'Bob');

$lenghtA = count($A);
$lenghtB = count($B);

for ($i=0; $i <= $lengthA; $i++)
{
  if ($A[i] == $B[i]) $C[] = $A[i];
  $i++;
  for ($j=0; $j <= $lengthB; $j++)
  {
    if ($A[j] == $B[j]) $C[] = $A[j];
    $j++;
  }
}

print_r($A);
echo ("<br>");
print_r($B);
echo ("<br>");
print_r($C);

?>

I hope everything is OK with algorithm, but my array C (3rd) is kinda empty.
Pleas help!

[laserlight]

At a glance, the first problem is that there is array out of bounds access since your loop indices start from 0 to the array length inclusive. The next problem is that you are using the undefined constant i as an index when you want to use the variable $i. Besides that, I am curious as to why you repeat the increments of $i and $j, and have two lines where you assign from $A into $C.

As for the algorithm itself: an efficient algorithm for computing the intersection involves sorting both the arrays and then making a single pass through each of them. Another efficient algorithm involves sorting one of the arrays, then making a single pass through the other array, using binary search on the first array.

[reQuorter]

Thanks for tips laserlight!

I've fixed my problem, here is my code:

<?php
$A = Array('Joe', 'Bob', 'Sarah', 'Bill', 'Suzy');
$B = Array('Joe', 'pos', 'suzy', 'Bob');
$C = Array();

$lengthA = count($A);
$lengthB = count($B);

for ($i=0; $i < $lengthA; $i++)
 for ($j=0; $j < $lengthB; $j++)
   if (($A[$i] == $B[$j]) && !in_array($A[$i], $C))
     $C[] = $A[$i];

print_r($A);
echo ('<br>');
print_r($B);
echo ('<br>');
print_r($C);
?>

[nrg_alpha]

I'm curious as to why you do not simply use array_intersect however:

$A = Array('Joe', 'Bob', 'Sarah', 'Bill', 'Suzy');
$B = Array('Joe', 'pos', 'suzy', 'Bob');
$C = array_intersect($A, $B);

echo '<pre>';
print_r($C);
echo '</pre>';

Array
(
    [0] => Joe
    [1] => Bob
)

Why complicate things? Am I simply misunderstanding something?

[laserlight]

nrg_alpha wrote:

I'm curious as to why you do not simply use array_intersect however:

It is mentioned in the first post: reQuorter wanted to try his/her hand at implementing an algorithm that mimics array_intersect().

[jazz_snob]

I actually had a very similar array task put to me at a job interview except the final array had to be sorted too...I don't remember exact details as it was about 10 months ago. I wasn't allowed to use any php array functions.

[laserlight]

jazz_snob wrote:

I actually had a very similar array task put to me at a job interview except the final array had to be sorted too.

If you use the first of the two efficient algorithms I outlined, the final array will indeed be sorted.