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

分别。

这给了你对数复杂度。

Answer 2

一旦你得到index元素的，你可以只scan forward and backwards检查那个元素。由于数组是sorted，所有的duplicates will be together. 在worst case所有元素都相同的情况下，此方法将采用O(n)

Answer 3

您的函数假定数组按降序排序。您可以对其进行修改以查找第一个匹配项的位置（如果有）并列出所有匹配项：

void list_all_matches(const int *array, int N, int chave) {
    int meio, inf = 0, sup = N; 
    while (inf < sup) {
        meio = inf + (sup - inf) / 2;
        if (chave < array[meio])
            sup = meio;
        else
            inf = meio;
    }
    while (sup < N && array[sup] == chave)
        printf("%d\n", sup++);
}