I am trying to perform a binary search on an array, and I must find all the occurrences of a string. I've tried with bsearch
, but I don't know how to do it.
/* data structures */
typedef struct {
char *name;
char *value;
} acronym;
struct {
acronym *tab;
size_t size;
} acronymArray;
/* code */
char buf[256];
fgets(buf, sizeof buf, stdin);
for (size_t i = 0; i < acronymArray.size; ++i)
if (!strcmp(buf, acronymArray.tab[i].name))
printf("Found: %s\n", acronymArray.tab[i].value);
/* How to translate it with a binary search ?
Of course my array was sorted with qsort previously */
I've tried this, but it works only for one occurrence :
if ((k = bsearch(k, acronymArray.tab, acronymArray.size, sizeof *acronymArray.tab, compare)))
printf("found : %s\n", k->value);
I thought about adding a boolean variable to my structure « acronym », but I'm not sure...
This is not homework.
It should be quite simple: you find any occurrence with binary search, and then look forward/backward from the found occurrence until you find something which is not equal to the found item (or until you find the sequence end). All the occurrences must be sequential in the sorted list.