Reputation: 31
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
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
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
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