CODEWITHSUNDEEP
cbinary-search
user2976298
user2976298

Reputation: 31

Binary Search in C

I implemented a search function of elements of the list that it was a binary search returns the index of the element found. My curiosity is to have a method of the binary search you could print all occurrences of the element in the list.

Below is the code

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;   
}

part of the other source

How could I make this code snippet only print occurrences duplicated?

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++;
    }
}

Upvotes: 1

Views: 2928

Answers (3)

chqrlie
chqrlie

Reputation: 145317

Your function assumes that the array is sorted in descending order. You can modify it to find the location of the first match, if any, and list all matches:

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++);
}

Upvotes: 1

Bartosz Marcinkowski
Bartosz Marcinkowski

Reputation: 6881

You can implement binary search two ways:

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

Using these two implementations combined you can easily determine the number of copies of each element.

If your array contains integeres only, you don't event have to use both - just pick one and search for

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

respectively.

That gives you logarithmic complexity.

Upvotes: 1

Keval Doshi
Keval Doshi

Reputation: 748

Once you get the index of the element, you can just scan forward and backwards checking for that element. As the array is sorted, all the duplicates will be together. In the worst case when all the elements are same, this method would take O(n)

Upvotes: 0

Related Questions