can bsearch tell me the index?

[Michiel Rapati-Kekkonen]

bsearch finds me only the first occurrence of something I'm looking for,
but I would like to know the place in the list where it is found.
The index of it's place in the array.
So that I can check if there are more to find on the next places.
I need to find all occurences.
Maybe anyone of you know even a better way?

thanks, in advance!

Michiel Rapati

 

[Peter Nilsson]

bsearch finds me only the first occurrence of something I'm looking for,
but I would like to know the place in the list where it is found.
The index of it's place in the array.
So that I can check if there are more to find on the next places.
I need to find all occurences.
Maybe anyone of you know even a better way?

If you call...

T *where = bsearch(key, base, N, sizeof *base, compar);

....then, assuming non null return, the index is...

size_t index = where - base;

From there, the simplest option is to iterate forwards and backwards from index to find
the equivalents. Or you can write your own customised search function. But that's really
an algorithm issue, and not topical in clc.

 

[Al Bowers]

bsearch finds me only the first occurrence of something I'm looking for,
but I would like to know the place in the list where it is found.
The index of it's place in the array.
So that I can check if there are more to find on the next places.
I need to find all occurences.
Maybe anyone of you know even a better way?

I do believe your approach is the best method for searching an
existing array. Once the array is sorted, use function bsearch
to search for the key value. If it is found, then search the
elements adjacent to the key element for duplicates.

Example using a integer array;

#include <stdio.h>
#include <stdlib.h>

#define SZ 6

void printarray(int *iia,const char *s);
int cmp(const void *v1, const void *v2);
void printfindmore(int *ia, int elemnr);

int main(void)
{
int key, *ip,elem,iarray[SZ] = {3,5,1,3,4,3};

printarray(iarray,"Unsorted");
qsort(iarray,SZ,sizeof *iarray,cmp);
printarray(iarray,"\nSorted Assending");
key = 3;
printf("\n\tSearching for value: %d\n",key);
ip = bsearch(&key,iarray,SZ,sizeof *iarray,cmp);
if(!ip)
printf("The value: %d was not found\n",key);
else
{
elem = ip - iarray;
printf("The value: %d was found at element %d\n",
key, elem);
printfindmore(iarray,elem);
}
return 0;
}

void printarray(int *ia,const char *s)
{
int i;

printf("\t%s\n",s);
for(i = 0; i < SZ; i++)
printf("array[%d] = %d\n",i,ia);
return;
}

int cmp(const void *v1, const void *v2)
{
const int *i1 = v1;
const int *i2 = v2;

return (*i1 < *i2)?-1*i1 != *i2);
}

void printfindmore(int *ia, int elemnr)
{
int i;

for(i = elemnr-1; i >= 0;i--)
{
if(ia != ia[elemnr]) break;
printf("Value %d was also found at element %d\n",
ia[elemnr],i);
}
for(i = elemnr+1; i < SZ; i++)
{
if(ia != ia[elemnr]) break;
printf("Value %d was also found at element %d\n",
ia[elemnr],i);
}
return;
}

 

[Al Bowers]

bsearch finds me only the first occurrence of something I'm looking for,

The Standard says that if 2 of the elements in the array compare equal,
the element that is matched is unspecified. Therefore the match may
not be the first occurrence.

 

[Darrell Grainger]

bsearch finds me only the first occurrence of something I'm looking for,

Actually, bsearch will return a pointer to some occurrence. If there is
more than one occurrence it can return a pointer to any of them.

but I would like to know the place in the list where it is found.
The index of it's place in the array.
So that I can check if there are more to find on the next places.
I need to find all occurences.
Maybe anyone of you know even a better way?

If I was searching an array of flogals then the code snippet might look
something like this:

flogals *result;
result = bsearch(key_i_desire,
array_of_flogals,
sizeof array_of_flogals / sizeof array_of_flogals[0],
sizeof array_of_flogals[0], compare_flogals);

Once I do this I can look at result[0]. I can also look at result[1] to
see if it is a match as well. I can also look at result[-1] but I have to
be careful that result != &array_of_flogals[0].

 

[Michiel Rapati-Kekkonen]

Even though I thanked you already in advance, I'll do it afterwards, too.
Your tips, they helped me perfectly out.

Michiel

 

[CBFalconer]

bsearch finds me only the first occurrence of something I'm
looking for,

Actually, bsearch will return a pointer to some occurrence. If
there is more than one occurrence it can return a pointer to any
of them.

but I would like to know the place in the list where it is
found. The index of it's place in the array. So that I can
check if there are more to find on the next places. I need to
find all occurences. Maybe anyone of you know even a better
way?

If I was searching an array of flogals then the code snippet
might look something like this:

flogals *result;
result = bsearch(key_i_desire,
array_of_flogals,
sizeof array_of_flogals / sizeof array_of_flogals[0],
sizeof array_of_flogals[0], compare_flogals);

Once I do this I can look at result[0]. I can also look at
result[1] to see if it is a match as well. I can also look at
result[-1] but I have to be careful that result != &array_of
_flogals[0].

That can be done with code such as:

flogals *resultop, *temp;
.... above code ....
resultop = temp = result;
if (result) {
while ((temp > &array_of_flogals[0]) &&
(0 == compare_flogals(*temp, temp[-1])) )
temp--;
result = temp;
/* set temp to ptr to last+1 of array_of_flogals */
temp = &array_of_flogals[sizeof array_of_flogals /
sizeof array_of_flogals[0]];
while ((resultop < temp) &&
(0 == compare_flogals(*resultop, resultop[1])) )
resultop++;
}
/* Now result through resultop all point to the searched
* for value, and there are no such values outside that
* range, or result and resultop are both NULL. */

(Untested)