c - C 中的二进制搜索

Question

我实现了列表元素的搜索功能，它是二分搜索返回找到的元素的索引。我的好奇心是有一种二进制搜索方法，您可以打印列表中出现的所有元素。

下面是代码

int Binary_Search(int *array, int chave , int N) {
    int inf = 0; 
    int sup = N-1; 
    int meio;
    while (inf <= sup) {
        meio = inf + (sup-inf)/2;
        if (chave == array[meio])
            return meio;
        else if (chave < array[meio])
            sup = meio-1;
        else
            inf = meio+1;
    }

    return -1;   
}

其他来源的一部分

我怎样才能让这个代码片段只打印重复的事件？

else {
    Imprime_Struct(Tabinvertida_Fornecedor[aux]->info);
    aux=aux+1;
    while (aux != i) {
        if (strcmp(chave, TabName[aux]->info.name)==0)
            Print_Struct(TabName[aux]->info);
        aux++;
    }
}

Answer 1

您可以通过两种方式实现二分查找:

1) so that it finds the first element not smaller than given
2) so that it finds the last element not greater than given

结合使用这两种实现，您可以轻松确定每个元素的副本数。

如果您的数组仅包含整数，则您不必同时使用两者 - 只需选择一个并搜索

1) n and n+1
2) n-1 and n

分别。

这给了你对数复杂度。