получить неправильный вывод в программе

Question

Я недавно написал программу, которая дает неправильный вывод, и у меня нет ни малейшего представления, почему.

Эта программа проверяет следующее: задано некоторое 'k' (значение) и два массива A и B, проверяя, есть ли какое-нибудь ' x ', которое принадлежит массиву A и ' y ', который принадлежит B , так что xk = y .

Вот мой код:

        #define _CRT_SECURE_NO_WARNINGS
        #include<stdio.h>
        #include<stdlib.h>

        int* buildArray(int size);
        int partition(int arr[], int low, int high);
        void quickSort(int *arr, int low, int high);
        int findValuesForDifference(int* A, int n, int* B, int m, int k);

        void main()
        {
            int n, m, k;
            int *A, *B;
            printf("please enter a number for the size of array A : ");
            scanf("%d", &n);
            printf("\nenter %d numbers for array A: ", n);
            A = buildArray(n);
            printf("please enter a number for the size of array B : ");
            scanf("%d", &m);
            printf("\nenter %d numbers for array A: ", m);
            B = buildArray(m);
            printf("\nplease enter a number for k: ");
            scanf("%d", &k);
            if (findValuesForDifference(A, n, B, m, k))
                printf("\nthere are some x which belongs to A and y which belongs to B such that x-y=k\n");
            else
                printf("\nthere are not any x which belongs to A and y which belongs to B such that x-y=k\n");

            free(B);
            free(A);
        }

        int findValuesForDifference(int* A, int n, int* B, int m, int k)
        {
            int low = 0, high = n - 1, middle, i;

            quickSort(A, low, high);

    /*using binary search sorted Array A, for each element of array B*/
            for (i = 0; i < m; i++)
            {
                while (low <= high)
                {
                    middle = (low + high) / 2;
                    if (k + B[i] == A[middle])
                        return 1;
                    else if (k + B[i] < A[middle])
                        high = middle - 1;
                    else
                        low = middle + 1;
                }
            }
            return 0;
        }

            int partition(int arr[], int low, int high)
            {
                int pivot = arr[high], i = (low - 1), j;

                for (j = low; j <= high - 1; j++)
                {

                    if (arr[j] <= pivot)
                    {
                        i++;    
                        swap(&arr[i], &arr[j]);
                    }
                }
                swap(&arr[i + 1], &arr[high]);
                return (i + 1);
            }

            void quickSort(int* arr, int low, int high)
            {
                int pivot;

                if (low < high)
                {
                    pivot = partition(arr, low, high);

                    quickSort(arr, low, pivot - 1);
                    quickSort(arr, pivot + 1, high);
                }
            }

           int* buildArray(int size)

           { int i; 
             int* arr = (int*)malloc(size * sizeof(int));       
             if (!arr) 
                 { printf("ERROR! Not enough memory!\n");  
                   exit(1); 
                 } 
             for (i = 0; i < size; i++) 
                  scanf("%d", &arr[i]); return arr; 
            }

Для массива A размером n=4 и элементов: 14 2 12 2 и массива B размером m=6 и элементов: 25 11 2 25 17 8 и k=3, Я получаю следующий неправильный вывод
there are not any x which belongs to A and y which belongs to B such that x-y=k,

пока ожидаемый результат there are some x which belongs to A and y which belongs to B such that x-y=k, потому что - например, есть 14, которые принадлежат A, и 11, которые принадлежат B, так что 14-11 = 3.

Answer 1

В вашей функции findValuesForDifference() вы задаете значения low и high только один раз при определении этих переменных.

Вам нужно сбрасывать их значения на каждой итерации основного цикла, иначе ваш двоичный поиск будет работать только один раз:

int findValuesForDifference(int *A, int n, int *B, int m, int k)
{
    int low, high, middle, i;

    quickSort(A, low, high);

    /* using binary search sorted Array A, for each element of array B */
    for (i = 0; i < m; i++) {
        low = 0;
        high = n - 1
        while (low <= high) {
            middle = (low + high) / 2;
            if (k + B[i] == A[middle])
                return 1;
            else if (k + B[i] < A[middle])
                high = middle - 1;
            else
                low = middle + 1;
        }
    }
    return 0;
}