c - 在程序中得到错误的输出

Question

我最近编写了一个程序，它给出了错误的输出，但我完全不知道为什么。

该程序检查以下内容:给定一些“k”(值)以及两个数组 A 和 B，检查是否有一些“x”属于数组 A 和属于 B 的 'y'，因此 x-k=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; 
            }

对于大小为 n=4 的数组 A 和元素: 14 2 12 2 ，以及大小为 m=6 的数组 B和元素:25 11 2 25 17 8 和 k=3， 我得到以下错误输出
不存在任何属于 A 的 x 和属于 B 的 y 使得 x-y=k,

而预期输出是 有一些 x 属于 A，y 属于 B，这样 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;
}