对动态分配的数组进行二进制搜索

Question

我正在开发一个程序，它从重定向的文件中获取输入并将该文件中的整数存储到一个动态数组中，直到读取 -999 如果我们尝试将更多的值放入它应该会增长由其当前大小持有。

我将这些值粘贴到执行二进制搜索的函数中，returns 找到的位置和查找所需的比较量。

但是，当我运行它时，我得到了数组中的所有值，包括所有空白处的零。因此我的位置变量和比较变量被丢弃了。它不是函数，因为它与硬编码数组完美配合。

所以我的问题是，有没有办法摆脱数组的那部分？谢谢

int var;
int counter = 0;

int *orgarr;
int size = 10;
orgarr = (int *) malloc (size * sizeof(int) );


int *tempo;
tempo = (int *) malloc (size * 2 * sizeof(int));
int i;
for ( i = 0 ; i < size ; i++)
    tempo[i] = orgarr[i];
    free (orgarr);
orgarr = tempo;
size = size * 2;

while (var != -999) {
    scanf("%i", &var);
    if (var != -999){
    orgarr[counter] = var;
    }
    counter++;
}

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

Answer 1

您需要将临时数组初始化为不会出现在重定向文件中的内容，例如 -1。这样在打印结果的循环中可以忽略该值。

for (i = 0; i < size; i++) {
    if(orgarr[i] != -1){
       printf("%i", orgarr[i]);
    }
}

你正在打印额外的零，因为数组没有被完全填满。希望这可以帮助！

Answer 2

您可以使用 realloc 来改变数组的大小。
如果指针设置为 NULL，realloc 将在第一次分配内存时表现得与 malloc 相同。
考虑使用“%d”。如果有任何带有前导零的值，例如 08，“%i”将尝试将它们读取为八进制值。对于 08，它将失败，011 将被读取为 9。但是如果您实际上有一些八进制值，您会希望继续使用 "%i"。
这将在每个输入上重新分配，您可以使用 counter 变量一次重新分配 10 个或根据需要加倍分配。
您也可以先分配 10,000，然后在读取所有输入后重新分配到正确的大小。

int var = 0;
int size = 0;
int *tempo = NULL;
int *orgarr = NULL;
while ( ( scanf ( "%d", &var)) == 1) {//invalid input or EOF will end loop
    if ( var != -999) {
        size++;
        tempo = realloc ( orgarr, size * sizeof ( int));
        if ( tempo) {
            orgarr = tempo;
            orgarr[size - 1] = var;
        }
        else {
            //realloc failed
            // return or break but somehow handle the problem
        }
    }
    else {
        break;//read -999
    }
}

对动态分配的数组进行二进制搜索

binary search on dynamically allocated array

c

arrays

dynamic

binary-search