是什么导致读取权限 violation/overflow？

Question

我正在尝试编写一个程序，通过选择排序对大小为 N 的数组进行排序，然后对该数组中的随机数进行二进制搜索并显示该数字所在的索引。我注意到如果没有我的二进制搜索功能，当 N 大于 1e5 时我开始出现堆栈溢出，当我尝试运行二进制搜索时我运行进入错误 "read access violation"。我将不胜感激任何帮助，尤其是考虑到我的 N 应该是 1e6。

   #define N 10
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

//function prototypes
void selectionSort(int array[], size_t length);
void swap(int* elementPtr, int* element2Ptr);
void printPass(int array[], size_t length, unsigned int pass, size_t index);
size_t binarySearch(const int b[], int searchKey, size_t low, size_t high);

unsigned long long int counter = 0;
unsigned long long int counter2 = 0;
long long unsigned int counter3 = 0;


int main(void) {
    int array[N];
    srand(time(NULL));
    for (size_t i = 0; i < N; i++) {
        array[i] = rand() % 90 + 10; // give each element a value
    }

    /*
    puts("Unsorted array:");

    for (size_t i = 0; i < N; i++) { //print the array
        printf("%d  ", array[i]);
    }
    puts("{\n");
    */

    selectionSort(array, N);

    /*
    puts("Sorted array:");

    for (size_t i = 0; i < N; i++) { //print the array
        printf("%d  ", array[i]);
    }
    */

    printf("\nTotal amount of comparisons: %d\n", counter);
    printf("Total amount of swaps: %d", counter2);

    int value = rand() % N + 1;
    int index = binarySearch(array, value, 0, N);
    printf("\nThe amount of times the value was compared was: %d\n", counter3);
    if (index != -1) {
        printf("%d was first found on index %d\n", value, index);
    }
    else printf("%d was not found on the array\n", value);

}


void selectionSort(int array[], size_t length) {
    //loop over length - 1 elements
    for (size_t i = 0; i < length - 1; i++) {
        size_t smallest = i; //first index of remaining array
        //loop to find index of smallest element
        for (size_t j = i + 1; j < length; j++) {
            counter++;
            if (array[j] < array[smallest]) {
                smallest = j;
            }
        }
        swap(array + i, array + smallest); //swap smallest element
        //printPass(array, length, i + 1, smallest); //output pass
    }
}

//function that swaps two elements in the array
void swap(int* elementPtr,int* element2Ptr)
{
    counter2++;
    int temp;
    temp = *elementPtr;
    *elementPtr = *element2Ptr;
    *element2Ptr = temp;

}

//function that prints a pass of the algorithm
void printPass(int array[], size_t length, unsigned int pass, size_t index) {
    printf("After pass %2d: ", pass);

    //output elements till selected item
    for (size_t i = 0; i < index; i++) {
        printf("%d ", array[i]);
    }
    printf("%d ", array[index]); //indicate swap

    //finish outputting array
    for (size_t i = index + 1; i < length; i++) {
        printf("%d ", array[i]);
    }
    printf("%s", "\n               "); //for alignment

    //indicate amount of array that is sorted
    for (unsigned int i = 0; i < pass; i++) {
        printf("%s", "-- ");
    }
    puts(""); //add newline
}

size_t binarySearch(const int b[], int searchKey, size_t low, size_t high) {
    counter3++;
    if (low > high) {
        return -1;
    }
    size_t middle = (low + high) / 2;

    if (searchKey == b[middle]) {
        return middle;
    }

    else if (searchKey < b[middle]) {
        return binarySearch(b, searchKey, low, middle - 1);
    }

    else {
        return binarySearch(b, searchKey, middle + 1, high);
    }
}

Answer 1

对于与 1e5 或 1e6 一样大的 N，您无法承受在堆栈上分配它。 int 的大小是 4 个字节，因此您将从堆栈中为您的数组消耗 4e5 个字节。

您将需要动态分配数组而不是

    int array[N];

你应该

    int *array = malloc(sizeof(int) * N);

完成所有操作后，别忘了

    free(array);

现在堆栈上应该有足够的 space 用于递归二进制搜索。

更新：

在我自己运行代码之后，确实，binarySearch 函数总是会产生分段错误。问题是参数的类型，即size_t。在某些情况下，binarySearch 函数的 high 参数变为 -1。但是因为 size_t 是一个无符号类型，你有一个整数下溢，因此 high 将变成 maxint。所以你的条件 if (low > high) 永远不会变成真的。您必须将 low 和 high 的类型更改为有符号整数才能使函数正常工作。

尽管如此，我还是建议进行动态分配，即使您的堆栈可能会处理这种情况。

Answer 2

即使在已发布的出色答案之外，我也看到了此代码的其他问题。我有问题运行 N = 2、N =5 和 N = 10。

我相信您在将变量传递到二进制搜索函数时遇到了一些问题。我认为您正在传递不正确的值，这些值会溢出并导致各种内存噩梦。这会导致您的读取访问冲突。

你的小箱子功能正常吗？尽管建议尽量减少您的足迹。我会仔细检查简单案例是否正常运行。

是什么导致读取权限 violation/overflow？

What's causing the read access violation/overflow?

c

recursion

overflow