1

I have two arrays, namely a[] and b[]. I would like to search if any element of a is present in b. Note that I do not want to find all duplicate occurrences, if any one element from a[] exists in b[], I would like to report it and break out without checking the rest of a[] or b[]

I'm a bit confused about how 'break' operates. Can 'break' break out of any kind of loop - for/while, but it breaks out of only the 'innermost loop' around where it's placed in code ?

This is my solution and please suggest if there is a better implementation for this O(n^2) approach

#include <stdio.h>

int main(void)
{
 int a[] = {1,2,3,4,5,6};
 int b[] = {11,2,3,7,8,9,6,10,11};
 int i = 0, j = 0;
 int duplicate = 0;

 for(i=0;i<sizeof(a)/sizeof(int);i++)
 {
  for(j=0;j<sizeof(b)/sizeof(int);j++)
  {
   if(a[i] == b[j])
   {
    printf("Duplicates found for [%d]\n",a[i]);
    duplicate = 1;
    break;
   }
  }

  if(duplicate == 1)
  {
   break;
  }
 }

 return 0;
}
IAMTubby
  • 1,627
  • 4
  • 28
  • 40
  • Can you sort the arrays? Instead of `O(n^2)` you can make the search in `O(2.n.log n + n)` which is the same as `O(n.log n)` – pmg Jun 23 '15 at 17:22
  • If you sort each array with an O(nlogn) sort such as quick sort or merge sort, then you could go through the arrays in O(n) time, yielding overall complexity of O(nlogn). – Adam Evans Jun 23 '15 at 17:22
  • And yes, `break` will break out of the nearest loop it finds, be it a `for` or a `while` – Ediac Jun 23 '15 at 17:23
  • Also ... a bigger indentation does not hurt compiler performance or executable speed and really really helps the programmer. – pmg Jun 23 '15 at 17:35

3 Answers3

3

break only breaks the innermost loop in which it is used. If you want to avoid the ugly syntax then you have multiple solutions:

  • ignore this optimization until you prove it's relevant
  • move the code inside a function that accepts the two arrays as arguments so that you can directly return from the function without having to break.
  • adjust indices i and j after that you found a duplicate to make both loops return gracefully
  • use a goto instruction (which is not advisable in any case)

Other solutions, with complexity lower than O(n^2) could require some additional data structure, like a hashset or sorting of data.

Jack
  • 131,802
  • 30
  • 241
  • 343
1

breaks generally break out of the most inner loop in c. You have used it correctly.

if u want to just report a duplicate, then u can put this code into a fuction and whenever a duplicate is found, you just return. The function would look like this:

//Here a and b are pointers to array 
//n1 and n2 are number of elements in array a,b
chk_dup(int *a,int *b,int n1,,int n2){

for(i=0;i<n1;i++)
 {
  for(j=0;j<n2;j++)
  {
   if(a[i] == b[j])
   {
    printf("Duplicates found for [%d]\n",a[i]);
    //duplicate = 1;
    //break;
    return;
   }
  }
 }
}

You cannot use sizeof(a) here becoz its just a pointer to array.Same goes for sizeof(b).

You can make this algorithm more efficient by sorting the arrays using quicksort(that would take O(nlgn)) and then for each element in a do binary search in b.

pseudo code for that is something like this:

//Here a and b are pointers to sorted arrays 
//n1 and n2 are number of elements in array a,b
chk_dup(int *a,int *b,int n1,,int n2){

for(i=0;i<n1;i++)
 {
   //find a[i] in b using binary search.
   int found=binary_search(a[i],b);
   if(found){
     printf("Found Duplicate");
     return;
   }
 }
 printf("No duplicate found");
}

So, the whole algorithm works in O(nlgn). While the algorithm you are using can take O(n^2).

Otherwise your code is perfectly fine and the use of break is correct

Yank Leo
  • 452
  • 5
  • 19
0

You could use goto as noted here How to break out of nested loops? it's the last remaining valid use of this...

And maybe there is a better solution using xor, not sure if you can reduce the

complexity though...

Community
  • 1
  • 1
orestiss
  • 2,183
  • 2
  • 19
  • 23