Блог

 **I need help here i have 2 arrays and i'm using merge sort and binary search to count the values that is the same in the 2 arrays but every time i got 0, i don't know why count dosn't work**
 

например:

ввод:

25 // размер первого массива

38 25 36 4 1 1 10 37 45 21 37 42 21 1 50 9 50 42 6 39 10 14 17 11 20 // первый массив

10 // размер второго массива

36 42 2 15 28 42 3 23 8 50 // второй массив

Я не могу получить результат 4, но я получил 0.

Мне нужна помощь здесь, у меня есть 2 массива, и я использую сортировку слиянием и двоичный поиск для подсчета значений, которые одинаковы в 2 массивах, но каждый раз, когда я получаю 0, я не знаю, почему подсчет не работает

например:

ввод:

25 // размер первого массива

38 25 36 4 1 1 10 37 45 21 37 42 21 1 50 9 50 42 6 39 10 14 17 11 20 // первый массив

10 // размер второго массива

36 42 2 15 28 42 3 23 8 50 // второй массив

Я не могу получить результат 4, но я получил 0.

 #include <stdio.h>

void merge(int arr[], int p, int q, int r) {

  int n1 = q - p   1;
  int n2 = r - q;

  int L[n1], M[n2];

  for (int i = 0; i < n1; i  )
    L[i] = arr[p   i];
  for (int j = 0; j < n2; j  )
    M[j] = arr[q   1   j];


  int i, j, k;
  i = 0;
  j = 0;
  k = p;


  while (i < n1 amp;amp; j < n2) {
    if (L[i] <= M[j]) {
      arr[k] = L[i];
      i  ;
    } else {
      arr[k] = M[j];
      j  ;
    }
    k  ;
  }

  while (i < n1) {
    arr[k] = L[i];
    i  ;
    k  ;
  }

  while (j < n2) {
    arr[k] = M[j];
    j  ;
    k  ;
  }
}

void mergeSort(int arr[], int l, int r) {
  if (l < r) {

    int m = l   (r - l) / 2;

    mergeSort(arr, l, m);
    mergeSort(arr, m   1, r);

    merge(arr, l, m, r);
  }
}

void binarySearch(int array[], int subarray[], int low, int high) {
  int count = 0;
  while (low <= high) {
    int mid = low   (high - low) / 2;

    for (int i = 0; i < high; i  )
    {
        if (array[mid] == subarray[i])
          count  ;

        if (array[mid] < subarray[i])
          low = mid   1;

        else
          high = mid - 1;
    }

  }

  printf("%dn", count);
}

int main()
{
    int n, m;
    int array[110000];
    int subarray[110000];

    scanf("%d", amp;n);

    for (int i = 0; i < n; i  )
    {
        scanf("%d", amp;array[i]);
    }

    mergeSort(array, 0, n - 1);

    scanf("%d", amp;m);

    for (int i = 0; i < m; i  )
    {
        scanf("%d", amp;subarray[i]);
    }

    binarySearch(array, subarray, 0, n - 1);

}
 

Пожалуйста, прочитайте комментарии в коде

 #include <stdio.h>

int binarySearch(int arr[], int l, int r, int x);
void merge(int arr[], int l, int m, int r);
void mergeSort(int arr[], int l, int r);
void printArray(int A[], int size);


int main()
{
    int n,m;
    do
    {
        printf("Give me the length of array 1 :");
        scanf("%d",amp;n);
    }while(n<1);

 int T1[n];//declaration of Array 1

do
{
    printf("Give me the length of array 2 :");
    scanf("%d",amp;m);
}while(m<1);

 int T2[m];//declaration of Array 2

 printf("The fill of Array 1:nn");

 for(int i=0;i<n;i  )
 {
     scanf("%d",amp;T1[i]);
 }

 printf("Given array is n");
 printArray(T1, n);

 mergeSort(T1, 0, n - 1);

 printf("nSorted array is n");
 printArray(T1, n);


 printf("The fill of Array 2:nn");

 for(int j=0;j<m;j  )
 {
     scanf("%d",amp;T2[j]);
 }

 printf("Given array is n");
 printArray(T2, m);

 mergeSort(T2, 0, m - 1);

 printf("nSorted array is n");

 printArray(T2, m);

 printf("nn");

 int x=0;

 for(int j=0;j<m;j  )
 {
    if(binarySearch(T1,0,n-1,T2[j])!=-1)
    {
        x  ;
    }
 }

 printf("nnBy using the 'Binary search' :");
 printf("nThe numbers of value repeated in Array 1 amp; Array 2 is :%dn",x);

return 0;

}





int binarySearch(int arr[], int l, int r, int x)
{
   while (l <= r)
   {
     int m = l   (r - l) / 2;

     // Check if x is present at mid
     if (arr[m] == x)
       return m;

     // If x greater, ignore left half
     if (arr[m] < x)
       l = m   1;

    // If x is smaller, ignore right half
    else
      r = m - 1;
 }
 // if we reach here, then element was
// not present
return -1;
}


void merge(int arr[], int l, int m, int r)
{
 int i, j, k;
 int n1 = m - l   1;
 int n2 = r - m;

 /* create temp arrays */
 int L[n1], R[n2];

 /* Copy data to temp arrays L[] and R[] */
 for (int i = 0; i < n1; i  )
 {
      L[i] = arr[l   i];
 }
  
 for (int j = 0; j < n2; j  )
 {
      R[j] = arr[m   1   j];
 }
 /* Merge the temp arrays back into arr[l..r]*/
 i = 0; // Initial index of first subarray
 j = 0; // Initial index of second subarray
 k = l; // Initial index of merged subarray     

 while (i < n1 amp;amp; j < n2)
 {
      if (L[i] <= R[j])
      {
          arr[k] = L[i];
          i  ;
      }
      else
      {
          arr[k] = R[j];
          j  ;
      }
      k  ;
}

/* Copy the remaining elements of L[], if there are any */

while (i < n1)
{
   arr[k] = L[i];
   i  ;
   k  ;
}

/* Copy the remaining elements of R[], if there are any */

while (j < n2)
{
    arr[k] = R[j];
    j  ;
    k  ;
}

}

/* l is for left index and r is right index of the sub-array of arr to be sorted */

void mergeSort(int arr[], int l, int r)
{
   if (l < r)
  {
      // Same as (l r)/2, but avoids overflow for
      // large l and h
      int m = (l   (r - l) / 2);

      // Sort first and second halves
      mergeSort(arr, l, m);
      mergeSort(arr, m 1, r);
      merge(arr, l, m, r);
}

}

/* UTILITY FUNCTIONS */
/* Function to print an array */
void printArray(int A[], int size)
{
   int i;
   for (i = 0; i < size; i  )
   {
         printf("%d ", A[i]);
   }

   printf("n");
}
 

Например:

Ввод:

25 // размер первого массива

38 25 36 4 1 1 10 37 45 21 37 42 21 1 50 9 50 42 6 39 10 14 17 11 20 // первый массив

10 // размер второго массива

36 42 2 15 28 42 3 23 8 50 // второй массив

Вывод: 4