By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
432,175 Members | 1,689 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 432,175 IT Pros & Developers. It's quick & easy.

can bsearch tell me the index?

P: n/a
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
Nov 14 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
"Michiel Rapati-Kekkonen" <no******@rapix.xx> wrote in message
news:10*************@corp.supernews.com...
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.

--
Peter
Nov 14 '05 #2

P: n/a


Michiel Rapati-Kekkonen wrote:
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[i]);
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[i] != 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[i] != ia[elemnr]) break;
printf("Value %d was also found at element %d\n",
ia[elemnr],i);
}
return;
}
--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapidsys.com (remove the x to send email)
http://www.geocities.com/abowers822/

Nov 14 '05 #3

P: n/a


Michiel Rapati-Kekkonen wrote:
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.

--
Al Bowers
Tampa, Fl USA
mailto: xa******@myrapidsys.com (remove the x to send email)
http://www.geocities.com/abowers822/

Nov 14 '05 #4

P: n/a
On Sun, 20 Jun 2004, Michiel Rapati-Kekkonen wrote:
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].

--
Send e-mail to: darrell at cs dot toronto dot edu
Don't send e-mail to vi************@whitehouse.gov
Nov 14 '05 #5

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

Michiel
Nov 14 '05 #6

P: n/a
Darrell Grainger wrote:
On Sun, 20 Jun 2004, Michiel Rapati-Kekkonen wrote:
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)

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!
Nov 14 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.