C 中的计数排序显然有效，但二进制搜索无效

Question

我正在寻求有关在第 3 周的 CS50 类(class)中实现计数排序功能的帮助。

必须对 int 数组进行排序。 我测试了各种未排序的数组，我的计数排序函数似乎对数组进行了正确的排序，但我的搜索函数在排序后的数组上不起作用。 有人可以给我提示吗？

void countsort( int array[], int size) {

    int count=0;
    int zahl=0;
    int max=65536;
    int countarr [max];
    int finalarr [size];

    memset (countarr, 0, sizeof(countarr));

    for(int i=0;i<size;i++) {
        zahl=array[i];
        countarr[zahl]++;
    }

    for(int i=0;i<max;i++) {

        while(countarr[i]>0) {
            finalarr[count]=i;
            countarr[i]--;
            count++;

        }
    }
    array=finalarr;

    for(int i=0;i<size;i++){
        printf(" %i ",array[i]);
    }
}

这是我在数组排序后使用的搜索算法，它与其他人的排序算法一起使用。

bool binarysearch(int value, int values[], int n){

    int start=0,
        end=n,
        mid=0,
        midpos=0;

    while(end>0) {

        midpos=(start+end)/2; 

        mid=values[midpos];

        if(mid==value) return true;

        if(mid<value) start=++midpos;

        if(mid>value) end=--midpos;

    }
    return false;
} 

Answer 1

1. 在binarysearch中，循环条件while(end>0)是错误的。 如果我们搜索一个大于数组中至少一个元素的值，end 永远不会为零。 尝试将其更改为 while(end>=start)，这实际上意味着所考虑的区间是非空的。

2. 在countsort 中，行array=finalarr; 没有复制整个数组。 相反，本地 变量array 变成指向finalarr 的指针。 原数组内容不变，退出函数时排序后的数组没有了。 这解释了为什么您的二进制搜索与其他排序函数一起工作(更好)。
   尝试将 finalarr[count]=i; 更改为 array[count]=i; 并完全摆脱 finalarr，将值放入 array 马上。 或者，您可以使用 memmove 代替该行。